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.