Algorithms for tolerated Tverberg partitions

DOI10.1007/978-3-642-45030-3_28MaRDI QIDQ2872094zbMATH OpenOpenAlexFDO

Authors Wolfgang Mulzer, Yannik Stein

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3452

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Computational aspects related to convexity (52B55)

Abstract: Let $P$ be a $d$-dimensional $n$-point set. A partition $T$ of $P$ is called a Tverberg partition if the convex hulls of all sets in $T$ intersect in at least one point. We say $T$ is $t$-tolerant if it remains a Tverberg partition after deleting any $t$ points from $P$. Sober'{o}n and Strausz proved that there is always a $t$-tolerant Tverberg partition with $lceiln/(d+1)(t+1)ceil$ sets. However, so far no nontrivial algorithms for computing or approximating such partitions have been presented. For $dleq2$, we show that the Sober'{o}n-Strausz bound can be improved, and we show how the corresponding partitions can be found in polynomial time. For $dgeq3$, we give the first polynomial-time approximation algorithm by presenting a reduction to the Tverberg problem with no tolerance. Finally, we show that it is coNP-complete to determine whether a given Tverberg partition is t-tolerant.

Recommendations

• ALGORITHMS FOR TOLERANT TVERBERG PARTITIONS
• Algorithms for Radon partitions with tolerance
• Algorithms for Radon partitions with tolerance
• New lower bounds for Tverberg partitions with tolerance in the plane
• Approximating Tverberg points in linear time for any fixed dimension

Cited in

(13)

• Path partitions and forward-only trellis algorithms
• Approximating Tverberg points in linear time for any fixed dimension
• Robust Tverberg and Colourful Carathéodory Results via Random Choice
• Horizontal partitions and Kleshchev's algorithm
• ALGORITHMS FOR TOLERANT TVERBERG PARTITIONS
• No-dimensional Tverberg Theorems and Algorithms
• Algorithms for Radon partitions with tolerance
• Tolerance for colorful Tverberg partitions
• No-dimensional Tverberg theorems and algorithms
• Algorithms for Radon partitions with tolerance
• New lower bounds for Tverberg partitions with tolerance in the plane
• Approximating Tverberg points in linear time for any fixed dimension
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

This page was built for publication: Algorithms for tolerated Tverberg partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2872094)