Approximating Tverberg Points in Linear Time for Any Fixed Dimension

Abstract

Let P be a d-dimensional n-point set. A Tverberg-partition of P is a partition of P into r sets P_1, ..., P_r such that the convex hulls conv(P_1), ..., conv(P_r) have non-empty intersection. A point in the intersection of the conv(P_i)'s is called a Tverberg point of depth r for P. A classic result by Tverberg implies that there always exists a Tverberg partition of size n/(d+1), but it is not known how to find such a partition in polynomial time. Therefore, approximate solutions are of interest. We describe a deterministic algorithm that finds a Tverberg partition of size n/4(d+1)^3 in time d^{O(log d)} n. This means that for every fixed dimension we can compute an approximate Tverberg point (and hence also an approximate centerpoint) in linear time. Our algorithm is obtained by combining a novel lifting approach with a recent result by Miller and Sheehy (2010).

14 pages, 2 figures. A preliminary version appeared in SoCG 2012. This version removes an incorrect example at the end of Section 3.1

Cited by in corpus (5)

• Algorithms for Tolerant Tverberg Partitions
• Stochastic Tverberg theorems and their applications in multi-class logistic regression, data separability, and centerpoints of data
• Computational Aspects of the Colorful Carathéodory Theorem
• No-dimensional Tverberg Theorems and Algorithms
• Resilient Distributed Vector Consensus Using Centerpoints