Near-Optimal Centerpoints in Polynomial Time in the Ambient Dimension
Kunal Dutta, Karol Pisula
原文摘要
An $α$-centerpoint of a set of $n$ input points is a point such that any halfspace containing it contains an $α$-fraction of the input. The first algorithm for centerpoints given by Clarkson, Eppstein, Miller, Sturtivant and Teng [IJCGA, 1996], the best quality centerpoint obtainable in polynomial time in $d$ has been $Ω(d^{-2})$; computing centerpoints of quality $Ω(d^{-1})$ required time $d^{Ω(d)}$. Recently Cherapanamjeri [FOCS, 2024] gave the first polynomial time randomized algorithm for computing \emph{approximate} $Ω(1/d)$-centerpoints, although the degree of the polynomial as well as associated constants, are large. We give a $\tilde{O}(d^5)$ time randomized algorithm for computing exact $Ω(1/(d\cdot\ln d\cdot\ln\ln d))$-centerpoints, improving significantly on the long-standing $Ω(1/d^2)$ quality bound of Clarkson et al. For low-dimensional point-sets, we also give the first algorithm with complexity subexponential in $d$, and independent of the bit-complexity, which achieves a $ω\pth{d^{-2}}$ quality of the centerpoint, improving on the previous $O(d^d)$ bound. For the Word RAM model, as well as for practical implementations, we also discuss a truncate-and-proceed approach to address bit-size complexity issues. On the way we also get a simple algorithm to compute $O(\sqrt{\frac{n}{d}})$-Tverberg partitions, and a point in the intersection of the convex hulls of the Tverberg parts. Our central idea is based on a lifting trick of Sarkaria [\emph{Isr. J. Math.} 1991], together with sampling ideas from Soberón [\emph{Combinatorica}, 2019], which we use to get a randomized algorithm for the \emph{Colorful Carathéodory} problem, improving upon the $d^{Θ(\log d)}$ run-time of Mulzer and Stein [SoCG, 2015]. Lastly, we also give applications of our improved bounds to several computational problems.
cs.CG