← 研踪 PaperTrailarXiv: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
摘要
An -centerpoint of a set of 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 has been ; computing centerpoints of quality required time . Recently Cherapanamjeri [FOCS, 2024] gave the first polynomial time randomized algorithm for computing \emph{approximate} -centerpoints, although the degree of the polynomial as well as associated constants, are large. We give a time randomized algorithm for computing exact -centerpoints, improving significantly on the long-standing quality bound of Clarkson et al. For low-dimensional point-sets, we also give the first algorithm with complexity subexponential in , and independent of the bit-complexity, which achieves a $ω\pth{d^{-2}}$ quality of the centerpoint, improving on the previous 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 -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 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
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-19 01:25 · 最新观测版本
Near-Optimal Centerpoints in Polynomial Time in the Ambient Dimension
An -centerpoint of a set of 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 has been ; computing centerpoints of quality required time . Recently Cherapanamjeri [FOCS, 2024] gave the first polynomial time randomized algorithm for computing \emph{approximate} -centerpoints, although the degree of the polynomial as well as associated constants, are large. We give a time randomized algorithm for computing exact -centerpoints, improving significantly on the long-standing quality bound of Clarkson et al. For low-dimensional point-sets, we also give the first algorithm with complexity subexponential in , and independent of the bit-complexity, which achieves a $ω\pth{d^{-2}}$ quality of the centerpoint, improving on the previous 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 -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 run-time of Mulzer and Stein [SoCG, 2015]. Lastly, we also give applications of our improved bounds to several computational problems.
查看此版本解读 →查看此版本原文 ↗