Abstract
Tverberg’s theorem states that for any k ≥ 2 and any set P ⊂ ℝ^d of at least (d + 1)(k  1) + 1 points, we can partition P into k subsets whose convex hulls have a nonempty intersection. The associated search problem lies in the complexity class PPAD ∩ 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 nodimensional 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 polynomialtime algorithm.
We present a deterministic algorithm that finds for any npoint set P ⊂ ℝ^d and any k ∈ {2, … , n} in O(nd ⌈log k⌉) time a kpartition of P such that there is a ball of radius O((k/√n)diam(P)) that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, and that there are no approximation algorithms that are truly polynomial in any dimension, 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 nodimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem.
BibTeX  Entry
@InProceedings{choudhary_et_al:LIPIcs:2020:12189,
author = {Aruni Choudhary and Wolfgang Mulzer},
title = {{NoDimensional Tverberg Theorems and Algorithms}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {31:131:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771436},
ISSN = {18688969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12189},
URN = {urn:nbn:de:0030drops121893},
doi = {10.4230/LIPIcs.SoCG.2020.31},
annote = {Keywords: Tverberg’s theorem, Colorful Carath{\'e}odory Theorem, Tensor lifting}
}
Keywords: 

Tverberg’s theorem, Colorful Carathéodory Theorem, Tensor lifting 
Collection: 

36th International Symposium on Computational Geometry (SoCG 2020) 
Issue Date: 

2020 
Date of publication: 

08.06.2020 