跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.24780 · v1

Near-Optimal Centerpoints in Polynomial Time in the Ambient Dimension

首次提交 2026-11-19 01:25
版本更新 2026-11-19 01:25
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

An αα-centerpoint of a set of nn 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 dd has been Ω(d−2)Ω(d^{-2}); computing centerpoints of quality Ω(d−1)Ω(d^{-1}) required time dΩ(d)d^{Ω(d)}. Recently Cherapanamjeri [FOCS, 2024] gave the first polynomial time randomized algorithm for computing \emph{approximate} Ω(1/d)Ω(1/d)-centerpoints, although the degree of the polynomial as well as associated constants, are large. We give a O~(d5)\tilde{O}(d^5) time randomized algorithm for computing exact Ω(1/(d⋅ln⁡d⋅ln⁡ln⁡d))Ω(1/(d\cdot\ln d\cdot\ln\ln d))-centerpoints, improving significantly on the long-standing Ω(1/d2)Ω(1/d^2) quality bound of Clarkson et al. For low-dimensional point-sets, we also give the first algorithm with complexity subexponential in dd, and independent of the bit-complexity, which achieves a $ω\pth{d^{-2}}$ quality of the centerpoint, improving on the previous O(dd)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(nd)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)d^{Θ(\log d)} run-time of Mulzer and Stein [SoCG, 2015]. Lastly, we also give applications of our improved bounds to several computational problems.

作者备注:A preliminary version appeared in the proceedings of SODA 2026

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-19 01:25 · 最新观测版本

Near-Optimal Centerpoints in Polynomial Time in the Ambient Dimension

An αα-centerpoint of a set of nn 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 dd has been Ω(d−2)Ω(d^{-2}); computing centerpoints of quality Ω(d−1)Ω(d^{-1}) required time dΩ(d)d^{Ω(d)}. Recently Cherapanamjeri [FOCS, 2024] gave the first polynomial time randomized algorithm for computing \emph{approximate} Ω(1/d)Ω(1/d)-centerpoints, although the degree of the polynomial as well as associated constants, are large. We give a O~(d5)\tilde{O}(d^5) time randomized algorithm for computing exact Ω(1/(d⋅ln⁡d⋅ln⁡ln⁡d))Ω(1/(d\cdot\ln d\cdot\ln\ln d))-centerpoints, improving significantly on the long-standing Ω(1/d2)Ω(1/d^2) quality bound of Clarkson et al. For low-dimensional point-sets, we also give the first algorithm with complexity subexponential in dd, and independent of the bit-complexity, which achieves a $ω\pth{d^{-2}}$ quality of the centerpoint, improving on the previous O(dd)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(nd)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)d^{Θ(\log d)} run-time of Mulzer and Stein [SoCG, 2015]. Lastly, we also give applications of our improved bounds to several computational problems.

查看此版本解读 →查看此版本原文 ↗