Computing Approximate Centerpoints in Polynomial Time

The centerpoint is arguably the most natural generalization of the median to higher dimensions. Intuitively, a centerpoint of a point set is such that any hyperplane passing through the point results in an approximately balanced partition of the point set. Helly's theorem guarantees the existence of a point with depth <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(1/d)$</tex> which is also known to be the best possible. On the other hand, polynomial time algorithms for approximating centerpoints only guarantee a point with depth <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(1/d^{2})$</tex>, established nearly three decades ago. Unfortunately, even the simpler problem of testing whether a candidate point is a centerpoint is hard. In this paper, we present a novel notion of approximation along with a new algorithmic approach that enables efficient computation of a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(1/d)-\mathbf{depth}$</tex> point. Our main result is a randomized algorithm that computes an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon -\mathbf{approximate}$</tex> centerpoint of depth <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(1/d)$</tex>; that is, the point returned by the algorithm is at most <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon$</tex> away from the halfspaces characterizing points of depth at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(1/d)$</tex> along any direction. Furthermore, the runtime of our algorithm is polynomial in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n, d, 1/\varepsilon, \log(1/\delta)$</tex> where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\delta$</tex> denotes the failure probability of the algorithm. Our approach is based on a reduction to the smoothed setting where each point is is given an independent Gaussian perturbation of scale <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon$</tex>. In contrast to prior work, our algorithm is based on techniques from continuous optimization and leverages a novel connection between the problem of testing an approximate centerpoint and the Radial Isotropic Transformation, a central tool with diverse applications in mathematics and computer science. We show that the solution to this testing problem yields an approximate separation oracle for the set of large depth points, enabling its use in a gradient-descent style approach to compute centerpoints.