Near-Optimal Centerpoints in Polynomial Time in the Ambient Dimension

An α-centerpoint of a set of $n$ input points in $\mathbb R^d$, is a point such that any halfspace containing it, also contains an α-fraction of the input points. Recently a remarkable result of Cherapanamjeri [FOCS, 2024] gave the first polynomial time randomized algorithm for computing $\Omega(1/d)$-centerpoints. Here we give a practical and efficient polynomial time randomized algorithm for computing $\Omega \left(\frac{1}{d\log^2d}\right)$-centerpoints of arbitrary pointsets. Our algorithm is significantly simpler to implement, though it gives slightly worse quality centerpoints, and improves on the longstanding $d^{O(d)}$ running time of Clarkson, Eppstein, Miller, Sturtivant and Teng [IJCGA, 1996] for obtaining such centerpoints.