Centerpoint (geometry)

From Wikipedia, the free encyclopedia

In statistics and computational geometry, the centerpoint is a generalization of the median to data in two or more dimensions. Given a set of points, any hyperplane that goes through a centerpoint divides the points in two roughly equal parts: the smaller part should have at least a 1/(d + 1) fraction of the points. Unlike the median, a centerpoint need not be one of the data points. Any 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 the Tukey median of a point set (the 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.

In computational geometry, the centerpoint helps to produce divide and conquer algorithms.

[edit] References

Edelsbrunner, Herbert (1987). Algorithms in combinatorial geometry. Berlin: Springer-Verlag. ISBN 0-387-13722-X.