10.4230/LIPICS.SOCG.2019.38
Fulek, Radoslav
Radoslav
Fulek0000-0001-8485-1774
Gärtner, Bernd
Bernd
Gärtner
Kupavskii, Andrey
Andrey
Kupavskii
Valtr, Pavel
Pavel
Valtr
Wagner, Uli
Uli
Wagner0000-0002-1494-0568
The crossing Tverberg theorem
LIPIcs
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2019
2019-07-17T10:35:04Z
2019-08-02T12:39:24Z
conference
https://research-explorer.app.ist.ac.at/record/6647
https://research-explorer.app.ist.ac.at/record/6647.json
9783959771047
1868-8969
1812.04911
559837 bytes
application/pdf
The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.