Centerpoint (geometry)

In statistics and computational geometry, the notion of centerpoint is a generalization of the median to data in higher-dimensional Euclidean space. Given a set of points in d-dimensional space, a centerpoint of the set is a point such that any hyperplane that goes through that point divides the set of points in two roughly equal subsets: the smaller part should have at least a 1/(d + 1) fraction of the points. Like the median, a centerpoint need not be one of the data points. Every non-empty set of points (with no duplicates) has at least one centerpoint. Closely related concepts are the Tukey depth of a point (the minimum number of sample points on one side of a hyperplane through the point) and a Tukey median of a point set (a point maximizing the Tukey depth). A centerpoint is a point of depth at least n/(d + 1), and a Tukey median must be a centerpoint, but not every centerpoint is a Tukey median. Both terms are named after John Tukey.

For another generalization of the median to higher dimensions, see geometric median.

Algorithms

For points in the Euclidean plane, a centerpoint may be constructed in linear time. In any dimension d, a Tukey median (and therefore also a centerpoint) may be constructed in time O(n^d − 1 + n log n).

A randomized algorithm that repeatedly replaces sets of d + 2 points by their Radon point can be used to compute an approximation to a centerpoint of any point set, in an amount of time that is polynomial in both the number of points and the dimension.

References

• Chan, Timothy M. (2004), "An optimal randomized algorithm for maximum Tukey depth", Proc. 15th ACM–SIAM Symp. on Discrete Algorithms (SODA 2004), pp. 430–436 .
• Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua (September 1996), "Approximating center points with iterated Radon points", Int. J. Computational Geometry & Applications 6 (3): 357–377, MR 97h:65010 .
• Edelsbrunner, Herbert (1987), Algorithms in combinatorial geometry, Berlin: Springer-Verlag, ISBN 0-387-13722-X .
• Jadhav, S.; Mukhopadhyay, A. (1994), "Computing a centerpoint of a finite planar set of points in linear time", Discrete & Computational Geometry 12 (1): 291–312, doi:10.1007/BF02574382 .