In statistics and computational geometry, the notion of centerpoint is a generalization of the median to data in higher-dimensional

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...

. 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 In geometry, the geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances ...

Existence

A simple proof of the existence of a centerpoint may be obtained using

Helly's theorem Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913,. but not published by him until 1923, by which time alternative proofs by and had already appeared. Helly's t ...

. 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. 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 In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of ''d'' + 2 points in R''d'' can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these convex ...

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 both the number of points and the dimension..

References

Citations

Sources

* . * . * . * {{citation , last1 = Jadhav , first1 = S. , last2 = Mukhopadhyay , first2 = A. , doi = 10.1007/BF02574382 , issue = 1 , journal =

Discrete and Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geome ...

, pages = 291–312 , title = Computing a centerpoint of a finite planar set of points in linear time , volume = 12 , year = 1994, doi-access = free . Euclidean geometry Multi-dimensional geometry Means