---
OA_place: repository
OA_type: green
_id: '13974'
abstract:
- lang: eng
  text: 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 Rd, one can find a partition
    X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common
    point. In this paper, we prove a trengthening 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 ⌊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 Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result
    generalizes to a result about simplices in Rd, d≥2.
acknowledgement: "Part of the research leading to this paper was done during the 16th
  Gremo Workshop on Open Problems (GWOP), Waltensburg, Switzerland, June 12–16, 2018.
  We thank Patrick Schnider for suggesting the problem, and Stefan Felsner, Malte
  Milatz, and Emo Welzl for fruitful discussions during the workshop. We also thank
  Stefan Felsner and Manfred Scheucher for finding, communicating the example from
  Sect. 3.3, and the kind permission to include their visualization of the point set.
  We thank Dömötör Pálvölgyi, the SoCG reviewers, and DCG reviewers for various helpful
  comments.\r\nR. Fulek gratefully acknowledges support from Austrian Science Fund
  (FWF), Project  M2281-N35. A. Kupavskii was supported by the Advanced Postdoc.Mobility
  Grant no. P300P2_177839 of the Swiss National Science Foundation. Research by P.
  Valtr was supported by the Grant no. 18-19158 S of the Czech Science Foundation
  (GAČR)."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
  full_name: Fulek, Radoslav
  id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
  last_name: Fulek
  orcid: 0000-0001-8485-1774
- first_name: Bernd
  full_name: Gärtner, Bernd
  last_name: Gärtner
- first_name: Andrey
  full_name: Kupavskii, Andrey
  last_name: Kupavskii
- first_name: Pavel
  full_name: Valtr, Pavel
  last_name: Valtr
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem.
    <i>Discrete and Computational Geometry</i>. 2024;72:831-848. doi:<a href="https://doi.org/10.1007/s00454-023-00532-x">10.1007/s00454-023-00532-x</a>
  apa: Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., &#38; Wagner, U. (2024).
    The crossing Tverberg theorem. <i>Discrete and Computational Geometry</i>. Springer
    Nature. <a href="https://doi.org/10.1007/s00454-023-00532-x">https://doi.org/10.1007/s00454-023-00532-x</a>
  chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli
    Wagner. “The Crossing Tverberg Theorem.” <i>Discrete and Computational Geometry</i>.
    Springer Nature, 2024. <a href="https://doi.org/10.1007/s00454-023-00532-x">https://doi.org/10.1007/s00454-023-00532-x</a>.
  ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing
    Tverberg theorem,” <i>Discrete and Computational Geometry</i>, vol. 72. Springer
    Nature, pp. 831–848, 2024.
  ista: Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2024. The crossing Tverberg
    theorem. Discrete and Computational Geometry. 72, 831–848.
  mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” <i>Discrete and Computational
    Geometry</i>, vol. 72, Springer Nature, 2024, pp. 831–48, doi:<a href="https://doi.org/10.1007/s00454-023-00532-x">10.1007/s00454-023-00532-x</a>.
  short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational
    Geometry 72 (2024) 831–848.
date_created: 2023-08-06T22:01:12Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-04-14T13:52:36Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-023-00532-x
external_id:
  arxiv:
  - '1812.04911'
  isi:
  - '001038546500001'
intvolume: '        72'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1812.04911
month: '09'
oa: 1
oa_version: Preprint
page: 831-848
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: M02281
  name: Eliminating intersections in drawings of graphs
publication: Discrete and Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '6647'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: The crossing Tverberg theorem
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 72
year: '2024'
...