2026-07-25T13:18:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10442 2024-03-12T11:57:29Z ddc:004 open_access

The Crossing Tverberg Theorem Fulek, Radoslav Gärtner, Bernd Kupavskii, Andrey Valtr, Pavel Wagner, Uli Discrete geometry Tverberg theorem Crossing Tverberg theorem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Radoslav Fulek and Bernd Gärtner and Andrey Kupavskii and Pavel Valtr and Uli Wagner 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.38 urn:nbn:de:0030-drops-104423 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.38 eng https://creativecommons.org/licenses/by/3.0/legalcode