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).
In fact, Tverberg proved that there is a "Tverberg point" if there are enough points (viz., (k-1)(d+1)+1). If you change points by convex sets (an obvious generalization) such a conclutions in not anymore true... of course I am thinking in d as the combinatorial dimension of the family of convex set instead of its geometric dimension.
ReplyDelete