New lower bounds for Tverberg partitions with tolerance in the plane

DOI10.1016/J.DAM.2020.02.007zbMATH Open1442.05020arXiv2002.09660OpenAlexW3008909305MaRDI QIDQ2192113FDOQ2192113

Sergey Bereg, Mohammadreza Haghpanah

Publication date: 29 June 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Let $P$ be a set $n$ points in a $d$-dimensional space. Tverberg's theorem says that, if $n$ is at least $(k-1)(d+1)+1$, then $P$ can be partitioned into $k$ sets whose convex hulls intersect. Partitions with this property are called {em Tverberg partitions}. A partition has tolerance $t$ if the partition remains a Tverberg partition after removal of any set of $t$ points from $P$. Tolerant Tverberg partitions exist in any dimension provided that $n$ is sufficiently large. Let $N(d,k,t)$ be the smallest value of $n$ such that tolerant Tverberg partitions exist for any set of $n$ points in $mathbb{R}^d$. Only few exact values of $N(d,k,t)$ are known. In this paper we establish a new tight bound for $N(2,2,2)$. We also prove many new lower bounds on $N(2,k,t)$ for $kge2$ and $tge1$.

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

Recommendations

• Algorithms for tolerated Tverberg partitions
• New lower bounds for weak Schur partitions
• On Tverberg partitions
• Tolerance for colorful Tverberg partitions
• New results on binary space partitions in the plane (extended abstract)
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• A New Lower Bound on Hadwiger-Debrunner Numbers in the Plane
• New results on binary space partitions in the plane
• Plane partitions. V: The TSSCPP conjecture
• ALGORITHMS FOR TOLERANT TVERBERG PARTITIONS

zbMATH Keywords

lower boundorder typeTverberg partitionTverberg's theorem

Mathematics Subject Classification ID

Partitions of sets (05A18)

Cites Work

• Title not available (Why is that?)
• A generalisation of Tverberg's theorem
• A Generalization of Radon's Theorem
• Multidimensional Sorting
• Enumerating order types for small point sets with applications
• On Sets Projectively Equivalent to the Vertices of a Convex Polytope
• 10 points in dimension 4 not projectively equivalent to the vertices of a convex polytope
• Lawrence oriented matroids and a problem of McMullen on projective equivalences of polytopes
• Projective equivalences of \(k\)-neighbourly polytopes
• Equal coefficients and tolerance in coloured Tverberg partitions
• Tverberg's Theorem at 50: Extensions and Counterexamples
• Tverberg’s theorem is 50 years old: A survey
• Robust Tverberg and Colourful Carathéodory Results via Random Choice
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• ALGORITHMS FOR TOLERANT TVERBERG PARTITIONS
• A note on the Tolerant Tverberg Theorem

Cited In (3)

• Tolerance for colorful Tverberg partitions
• Tverberg’s theorem is 50 years old: A survey
• Algorithms for Radon partitions with tolerance

This page was built for publication: New lower bounds for Tverberg partitions with tolerance in the plane

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