Abstract:

The centerpoint theorem is one of the fundamental theorems in discrete geometry, and it states the following: given any set P of n points in Rd, there exists a point q such that any closed half-space containing q contains at least n/(d+1) points of P. The point q need not be a point of P. This theorem has found several applications in combinatorial geometry, statistics, geometric algorithms and related areas. An even more fundamental theorem, encompassing the centerpoint theorem, was first proven by Tverberg in 1966: Given any set P of n-points in d-dimensions, one can partition P into (roughly) n/(d+1) -sets, each of d+1 points, such that the Simplices spanned by the sets have a non-empty intersection(Tverberg's Theorem).

Tverberg's and Vrecica gave an ingenious algorithmic proof of Tverberg's Theorem. In the talk we will see its proof and two more fundamental results of geometry centerpoint theorem and Helley's Theorem using the same technique. We will see a generalization of the centerpoint theorem to a new theorem about "centerdisk" by extending this nice idea to such that the centerpoint theorem becomes a special case of this more general statement:

If there exists a disk D such that any half-space containing D contains a larger fraction of points of P than n/(d+1)? In the talk we will see the Upper and lower bounds of this question.

Host: Gerth Stølting Brodal