Improved approximation algorithms for Tverberg partitions

Sariel Har-Peled, Timothy Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication29th Annual European Symposium on Algorithms, ESA 2021
EditorsPetra Mutzel, Rasmus Pagh, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772044
StatePublished - Sep 1 2021
Event29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Portugal
Duration: Sep 6 2021Sep 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference29th Annual European Symposium on Algorithms, ESA 2021
CityVitual, Lisbon


  • Geometric spanners
  • Robustness
  • Vertex failures

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Improved approximation algorithms for Tverberg partitions'. Together they form a unique fingerprint.

Cite this