Wednesday, June 09, 2004

Tverberg Points

Inspired by Algorithms for Center and Tverberg Points by Pankaj K. Agarwal, Micha Sharir, and Emo Welzl:

Usually, checking if a point satisfies property X is easier than finding a point that satisfies property X. Tverberg points are an example of a rather bizarre reversal of this situation.

Suppose I take a collection of points in the plane, and partition it into subsets cleverly so that the convex hulls of the subsets all intersect in at least one point. Such a point is called a Tverberg Point. It was shown by Tverberg that such a point always exists. However, the following problem has unknown complexity in three dimensions:

Given a point p and a set of points P, is p a Tverberg point of P

The Tverberg point is one among a family of nonparametric notions of "deep" points in a point set. Other notions are the centerpoint (a point that "sees" the maximum number of points no matter which direction it looks in), and the Radon point (a Tverberg point where you partition P into two pieces).

Disqus for The Geomblog