ALGORITHMS FOR TOLERANT TVERBERG PARTITIONS
Wolfgang Mulzer, YANNIK STEIN · International Journal of Computational Geometry & Applications · 2014
Let P be a d-dimensional n-point set. A partition [Formula: see text] of P is called a Tverberg partition if the convex hulls of all sets in [Formula: see text] intersect in at least one point. We say that [Formula: see text] is t-tolerant if it remains a Tverberg partition after deleting any t points from P. Soberón and Strausz proved that there is always a t-tolerant Tverberg partition with ⌈n/(d + 1)(t + 1)⌉ sets. However, no nontrivial algorithms for computing or approximating such partitions have been presented so far. For d ≤ 2, we show that the Soberón-Strausz bound can be improved, and we show how the corresponding partitions can be found in polynomial time. For d ≥ 3, we give the first polynomial-time approximation algorithm by presenting a reduction to the regular Tverberg problem (with no tolerance). Finally, we show that it is coNP-complete to determine whether a given Tverberg partition is t-tolerant.