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 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 both the number of points and the dimension.[3]
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.
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.
February 06, 2023
centerpoint, geometry, statistics, computational, geometry, notion, centerpoint, generalization, median, data, higher, dimensional, euclidean, space, given, points, dimensional, space, centerpoint, point, such, that, hyperplane, that, goes, through, that, poin. 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 Contents 1 Related concepts 2 Existence 3 Algorithms 4 References 4 1 Citations 4 2 SourcesRelated concepts EditClosely 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 EditA 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 EditFor 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 both the number of points and the dimension 3 References EditCitations Edit Jadhav amp Mukhopadhyay 1994 Chan 2004 Clarkson et al 1996 Sources Edit 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 PDF International Journal of Computational Geometry amp Applications 6 3 357 377 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 Retrieved from https en wikipedia org w index php title Centerpoint geometry amp oldid 1115017023, wikipedia, wiki, book, books, library,
