Approximate centerpoints with proofs

作者：Miller Gary L; Sheehy Donald R^*

来源：Computational Geometry-Theory and Applications, 2010, 43(8): 647-654.

DOI：10.1016/j.comgeo.2010.04.006

We present the ITERATED TVERBERG algorithm, the first deterministic algorithm for computing an approximate centerpoint of a set S subset of R(d) with running time sub-exponential in d. The algorithm is a derandomization of the ITERATEDRADON algorithm of Clarkson et al. (International Journal of Computational Geometry and Applications 6 (3) (1996) 357-377) and is guaranteed to terminate with an Omega(1/d(2))-center. Moreover, it returns a polynomial-time checkable proof of the approximation guarantee, despite the coNP-completeness of testing centerpoints in general. We also explore the use of higher order Tverberg partitions to improve the running time of the deterministic algorithm and improve the approximation guarantee for the randomized algorithm. In particular, we show how to improve the Omega(1/d(2))-center of the ITERATEDRADON algorithm to Omega(1/d(r)/(r-1)) for a cost of O((rd)(d)) in time for any integer r > 1.

• 出版日期2010-10