• HOME
• 講演会情報

### 講演会情報

Extending Two Fundamental Theorems in Discrete Geometry

In this talk, we generalize two fundamental theorems in discrete geometry: The centerpoint theorem and ham sandwich theorem.

The centerpoint theorem is a well-known and widely used result in discrete geometry. It states that for any point set P of n points in the d-dimensional Euclidean space, there is a point c, not necessarily from P, such that each halfspace containing c contains at least n/(d+1) points of P. Such a point c is called a centerpoint, and it can be viewed as a generalization of a median to higher dimensions. In other words, a centerpoint can be interpreted as a good representative for the point set P. But what if we allow more than one representative? For example in one-dimensional data sets, often certain quantiles are chosen as representatives instead of the median. We present a possible extension of the concept of quantiles to higher dimensions. The idea is to find a set Q of (few) points such that every halfspace that contains one point of Q contains a large fraction of the points of P and every halfspace that contains more of Q contains an even larger fraction of P. This setting is comparable to the well-studied concepts of weak ε-nets and weak ε-approximations, where it is stronger than the former but weaker than the latter.

Then we talk about a generalization of the ham sandwich theorem. Assume you have a pizza consisting of four ingredients (e.g., bread, tomatoes, cheese and olives) that you want to share with your friend. You want to do this fairly, meaning that you and your friend should get the same amount of each ingredient. How many times do you need to cut the pizza so that this is possible? We will show that two straight cuts always suffice. More formally, we will show the following extension of the well-known Ham-sandwich theorem: Given four mass distributions in the plane, they can be simultaneously bisected with two lines. That is, there exist two oriented lines with the following property: let U be the region of the plane that lies to the positive side of both lines and let V be the region of the plane that lies to the negative side of both lines. Then W = U ∪ V contains exactly half of each mass distribution. Additionally, we prove that five mass distributions in the 3-dimensional Euclidean space can be simultaneously bisected by two planes.