Yannik Stein

Tolerated Tverberg Partitions: An Algorithmic Approach

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Master of Science (M.Sc.)
Abgabedatum: 28.03.2013
Homepage des Autors:

Kurzbeschreibung

Let $P$ be some point set in $R^d$. A t-tolerated Tverberg partition of $P$ is a partition into disjoint subsets $P_1,P_2,...,P_m$ whose convex hulls have a nonempty intersection even if up to $t$ points from $P$ are removed. Soberon and Strausz proved the existence of a t-tolerated Tverberg partition of size $m$ for each point set of size at least $(t+1)(m-1)(d+1)+1$. It is conjectured that this bound is tight.

As tolerated Tverberg partitions have not been studied in the context of algorithmics so far, this thesis focuses on the development of algorithms that compute such partitions. We present an algorithm that improved the bound by Soberon and Strausz in one dimension and for many cases in two dimensions. Two deterministic approximation algorithms exist for the special case of untolerated Tverberg partitions (i.e., $t=0$). In order to adapt these algorithms, we developed several approximation preserving reductions to the untolerated Tverberg problem. While the complexity of actually computing a t-tolerated Tverberg partition is still unknown, we could prove the coNP-completeness of a related decision problem.