Improved Approximation Algorithms for Tverberg Partitions

DOI10.4230/LIPICS.ESA.2021.51MaRDI QIDQ6075943zbMATH OpenOpenAlexFDO

Authors Sariel Har-Peled

Publication date 20 September 2023

Full work available at URL https://arxiv.org/abs/2007.08717

zbMATH Keywords

geometric spannersrobustnessvertex failures

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: $$ Tverberg's theorem states that a set of $n$ points in $R{e}^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(d^2)}$ 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.

Cited in

(5)

• Better Approximations for the Minimum Common Integer Partition Problem
• ALGORITHMS FOR TOLERANT TVERBERG PARTITIONS
• Algorithms for Radon partitions with tolerance
• No-dimensional Tverberg partitions revisited
• No-dimensional Tverberg partitions revisited

This page was built for publication: Improved Approximation Algorithms for Tverberg Partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075943)