Home Bookmarks Papers Blog

# Improved Approximation Algorithms for Tverberg Partitions

Sariel Har-Peled, and Timothy Zhou.
Tverberg's theorem states that a set of $n$ points in $\Re^d$ can be partitioned into $\ceil{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^2)}$ 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.
PDF. : arXiv.