Approximate centerpoints with proofs
Approximate centerpoints with proofs
复制标题
近似中心点与证明
DOI：
10.1016/j.comgeo.2010.04.006
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Don Sheehy
中科院分区：
文献类型：
--
作者：
G. Miller;Don Sheehy
给出了计算运行时间在d中次指数的S∈集的近似中心点的第一个确定性算法Iterated-Tverberg算法，该算法是Clarkson等人的Iterated-Radon算法的去随机化，并保证以O(1/D2)-中心终止.此外，尽管测试中心点通常是coNP-Completenes的，但它返回了近似保证的多项式时间可检查证明。我们还探索了使用高阶Tverberg划分来改善确定性算法的运行时间，并提高了随机化算法的逼近保证。特别地，我们证明了如何将迭代Radon算法的O(1/d2)中心改进为O(1/dr/(r-1))，而对于任意整数r，时间代价为O((Drd)d)。
We present the Iterated-Tverberg algorithm, the first deterministic algorithm for computing an approximate centerpoint of a set S ∈ Rdwith running time sub-exponential in d. The algorithm is a derandomization of the Iterated-Radon algorithm of Clarkson et al and is guaranteed to terminate with an O(1/d2)-center. Moreover, it returns a polynomial-time checkable proof of the approximation guarantee, despite the coNP-Completenes of testing centerpoints in general. We also explore the use of higher order Tverberg partitions to improve the runtime of the deterministic algorithm and improve the approximation guarantee for the randomized algorithm. In particular, we show how to improve the O(1/d2)-center of the Iterated-Radon algorithm to O(1/dr/(r-1)) for a cost of O((rd)d) in time for any integer r.