跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+979新增论文
+781其中 AI 相关
+119已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-20 08:48 · 全站最近入库:2026-11-20 19:58各信源进度 →

统计口径与数据新鲜度

统计 2026-11-20 06:13 — 2026-11-21 06:13(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-20 08:48最近发现新增版本:2026-11-20 19:58库内论文最新更新时间:2026-11-20 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

28,961 已收录论文24,030 AI 相关8,912 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 1 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-20 08:46(北京时间)
新论文 · v1arXiv:2611.24780

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