Computing Approximate Centerpoints in Polynomial Time
Yeshwanth Cherapanamjeri · 2024
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$\Omega(1/d)$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$\Omega(1/d^{2})$, 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$\Omega(1/d)-\mathbf{depth}$point. Our main result is a randomized algorithm that computes an$\varepsilon -\mathbf{approximate}$centerpoint of depth$\Omega(1/d)$; that is, the point returned by the algorithm is at most$\varepsilon$away from the halfspaces characterizing points of depth at least$\Omega(1/d)$along any direction. Furthermore, the runtime of our algorithm is polynomial in$n, d, 1/\varepsilon, \log(1/\delta)$where$\delta$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$\varepsilon$. 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.