No-Dimensional Tverberg Theorems and Algorithms
Open Access
- 12 April 2022
- journal article
- research article
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 68 (4) , 964-996
Abstract
Tverberg’s theorem states that for any $$k\ge 2$$ and any set $$P\subset {\mathbb {R}}^d$$ of at least $$(d+1)(k-1)+1$$ points in d dimensions, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem of finding the partition lies in the complexity class $$\text {CLS} = \text {PPAD} \cap \text {PLS}$$ , but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa (SODA 2019) gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set $$P\subset {\mathbb {R}}^d$$ and any $$k\in \{2,\dots ,n\}$$ in $$O(nd\lceil {\log k}\rceil )$$ time a k-partition of P such that there is a ball of radius $$O((k/\sqrt{n}){\text {diam}}(P))$$ that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria’s method (Israel Journal Math., 1992) to reduce the Tverberg problem to the colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem.
Keywords
All Related Versions
Funding Information
- European Research Council (StG 757609)
This publication has 31 references indexed in Scilit:
- A Geometric Proof of the Colored Tverberg TheoremDiscrete & Computational Geometry, 2011
- Approximate centerpoints with proofsComputational Geometry, 2010
- Generalized Ham-Sandwich CutsDiscrete & Computational Geometry, 2009
- Slicing Convex Sets and Measures by a HyperplaneDiscrete & Computational Geometry, 2007
- Partitions of Points into Simplices withk-dimensional Intersection. Part I: The Conic Tverberg’s TheoremEuropean Journal of Combinatorics, 2001
- The colored Tverberg's problem and complexes of injective functionsJournal of Combinatorial Theory, Series A, 1992
- A generalization of the ham sandwich theoremMathematical Notes, 1992
- A Colored Version of Tverberg's TheoremJournal of the London Mathematical Society, 1992
- A generalization of Radon's theorem IIBulletin of the Australian Mathematical Society, 1981
- A Generalization of Radon's TheoremJournal of the London Mathematical Society, 1966