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.
Related concepts
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 a different generalization of the median to higher dimensions, see geometric median.
Existence
A simple proof of the existence of a centerpoint may be obtained using Helly's theorem. Suppose there are n points, and consider the family of closed half-spaces that contain more than dn/(d + 1) of the points. Fewer than n/(d + 1) points are excluded from any one of these halfspaces, so the intersection of any subset of d + 1 of these halfspaces must be nonempty. By Helly's theorem, it follows that the intersection of all of these halfspaces must also be nonempty. Any point in this intersection is necessarily a centerpoint.
Algorithms
For points in the Euclidean plane, a centerpoint may be constructed in linear time.[1] In any dimension d, a Tukey median (and therefore also a centerpoint) may be constructed in time O(nd − 1 + n log n).[2]
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 the sense that its Tukey depth is linear in the sample set size, in an amount of time that is polynomial in the dimension.[3][4]
References
Citations
Sources
- 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, ISBN 978-0-89871-558-3.
- Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua (September 1996), "Approximating center points with iterated Radon points" (PDF), International Journal of Computational Geometry & Applications, 6 (3): 357–377, doi:10.1142/S021819599600023X, MR 1409651.
- 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 and Computational Geometry, 12 (1): 291–312, doi:10.1007/BF02574382.
- Har-Peled, S.; Jones, M. (2020-12-31), "Journey to the Center of the Point Set", ACM Transactions on Algorithms, 17 (1): 9:1–9:21, doi:10.1145/3431285, ISSN 1549-6325.