Centerpoint (geometry)

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. Like 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.

References