Algorithms for tolerated Tverberg partitions

DOI10.1007/978-3-642-45030-3_28zbMATH Open1406.68122arXiv1306.3452OpenAlexW1810719811MaRDI QIDQ2872094FDOQ2872094

Authors: Wolfgang Mulzer, Yannik Stein 

Publication date: 14 January 2014

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

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.

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

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

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)

Cited In (13)

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

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)