In statistics and computational geometry, the notion of centerpoint is a generalization of the median to data in higher-dimensional Euclidean space.
A simple proof of the existence of a centerpoint may be obtained using Helly's theorem.
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.