Improved Approximation Algorithms for Tverberg Partitions

2020/07/17 by Har-Peled, Sariel, Zhou, Timothy
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2007.08717

Abstract

\newcommand\floor[1]\lfloor #1 \rfloor \renewcommand\Reℝ Tverberg's theorem states that a set of n points in \Re^d can be partitioned into \floorn/(d+1) sets with a common intersection. A point in this intersection (aka Tverberg point) is a centerpoint of the input point set, and the Tverberg partition provides a compact proof of this, which is algorithmically useful. Unfortunately, computing a Tverberg point exactly requires n^O(d2) time. We provide several new approximation algorithms for this problem, which improve either the running time or quality of approximation, or both. In particular, we provide the first strongly polynomial (in both n and d) approximation algorithm for finding a Tverberg point.

Related

• Algorithms for Tverberg's theorem via centerpoint theorems
• A generalization of Tverberg's Theorem
• Tverberg theorems over discrete sets of points
• Tverberg plus constraints
• Tverberg Partition Graphs