Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Algorithms for Tolerated Tverberg Partitions
verfasst von : Wolfgang Mulzer, Yannik Stein
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
P
be a
d
-dimensional
n
-point set. A partition
$\mathcal{T}$
of
P
is called a
Tverberg
partition if the convex hulls of all sets in
$\mathcal{T}$
intersect in at least one point. We say
$\mathcal{T}$
is
t-tolerated
if it remains a Tverberg partition after deleting any
t
points from
P
. Soberón and Strausz proved that there is always a
t
-tolerated Tverberg partition with ⌈
n
/ (
d
+ 1)(
t
+ 1) ⌉ sets. However, so far no nontrivial algorithms for computing or approximating such partitions have been presented.
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 (untolerated) Tverberg problem. Finally, we show that it is coNP-complete to determine whether a given Tverberg partition is
t
-tolerated.