2026-08-14T17:03:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14632 2024-03-06T10:54:29Z ddc:004 open_access

Improved Approximation Algorithms for Tverberg Partitions Har-Peled, Sariel Zhou, Timothy Geometric spanners vertex failures robustness Tverberg’s theorem states that a set of n points in ℝ^d 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 n^{O(d²)} 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sariel Har-Peled and Timothy Zhou 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.51 urn:nbn:de:0030-drops-146323 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.51 eng https://creativecommons.org/licenses/by/4.0/legalcode