Computing the center of planar point sets
Jiřı́ Matoušek · DIMACS series in discrete mathematics and theoretical computer science · 1991
Given a collection H of n lines in the plane, the level of a point x is the number of lines of H lying below x or passing thru x. We show that for a given k, one can compute the convex hull of the set of points of level k, in time O(n log n). This implies that a description of the set of centerpoints of a given n-point set in the plane can be found within the same time bound, and a point of greatest Tukey depth (Tukey median) for a n-point set can be computed in time O(n log n). We also mention the computation of an approximate centerpoint in higher dimension.