@inproceedings{ecc7c52e556945dfbc3452a72b2ab575,
title = "Improved approximation algorithms for Tverberg partitions",
abstract = "Tverberg's theorem states that a set of n points in Rd can be partitioned into ⌈n/(d + 1)⌉ sets whose convex hulls all intersect. A point in the intersection (aka Tverberg point) is a centerpoint, or high-dimensional median, of the input point set. While randomized algorithms exist to find centerpoints with some failure probability, a partition for a Tverberg point provides a certificate of its correctness. Unfortunately, known algorithms for computing exact Tverberg points take nO(d2) time. We provide several new approximation algorithms for this problem, which improve running time or approximation quality over previous work. In particular, we provide the first strongly polynomial (in both n and d) approximation algorithm for finding a Tverberg point.",
keywords = "Geometric spanners, Robustness, Vertex failures",
author = "Sariel Har-Peled and Timothy Zhou",
note = "Funding Information: Funding Sariel Har-Peled: Work on this paper was partially supported by a NSF AF award CCF-1907400. Timothy Zhou: Work on this paper was partially supported by a NSF AF award CCF-1907400. Publisher Copyright: {\textcopyright} Sariel Har-Peled and Timothy Zhou; licensed under Creative Commons License CC-BY 4.0; 29th Annual European Symposium on Algorithms, ESA 2021 ; Conference date: 06-09-2021 Through 08-09-2021",
year = "2021",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.ESA.2021.51",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Petra Mutzel and Rasmus Pagh and Grzegorz Herman",
booktitle = "29th Annual European Symposium on Algorithms, ESA 2021",
address = "Germany",
}