Document Open Access Logo

The Crossing Tverberg Theorem

Authors Radoslav Fulek , Bernd Gärtner, Andrey Kupavskii, Pavel Valtr , Uli Wagner

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2019.38.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
  • Theory of computation → Computational geometry
Keywords
  • Discrete geometry
  • Tverberg theorem
  • Crossing Tverberg theorem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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.

Cite As Get BibTex

Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. The Crossing Tverberg Theorem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.38

Author Details

Radoslav Fulek
  • IST Austria, Klosterneuburg, Austria
Bernd Gärtner
  • Department of Computer Science, ETH Zürich, Switzerland
Andrey Kupavskii
  • University of Oxford, UK
  • Moscow Institute of Physics and Technology, Russia
Pavel Valtr
  • Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
  • Department of Computer Science, ETH Zürich, Switzerland
Uli Wagner
  • IST Austria, Klosterneuburg, Austria

Funding

  • Fulek, Radoslav: The author gratefully acknowledges support from Austrian Science Fund (FWF), Project M2281-N35.
  • Kupavskii, Andrey: The research was supported by the Advanced Postdoc.Mobility grant no. P300P2_177839 of the Swiss National Science Foundation.
  • Valtr, Pavel: Research by P. Valtr was supported by the grant no. 18-19158S of the Czech Science Foundation (GAČR).

Acknowledgements

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 and communicating the example from Section 3.2. We thank Dömötör Pálvölgyi and the SoCG reviewers for various helpful comments.

References

  1. José Luis Alvarez-Rebollar, Jorge Cravioto Lagos, and Jorge Urrutia. Crossing families and self crossing Hamiltonian cycles. XVI Encuentros de Geometría Computacional, page 13, 2015. Google Scholar
  2. B. Aronov, P. Erdős, W. Goddard, D. J. Kleitman, M. Klugerman, J. Pach, and L. J. Schulman. Crossing families. Combinatorica, 14(2):127-134, 1994. Google Scholar
  3. Sergey Avvakumov, Isaac Mabillard, Arkadiy Skopenkov, and Uli Wagner. Eliminating higher-multiplicity intersections, III. Codimension 2. Preprint, https://arxiv.org/abs/1511.03501, 2015.
  4. Martin Balko, Radoslav Fulek, and Jan Kynčl. Crossing Numbers and Combinatorial Characterization of Monotone Drawings of K_n. Discrete &Computational Geometry, 53(1):107-143, 2015. Google Scholar
  5. Imre Bárány, Senya B Shlosman, and András Szücs. On a topological generalization of a theorem of Tverberg. Journal of the London Mathematical Society, 2(1):158-164, 1981. Google Scholar
  6. Imre Bárány and Pablo Soberón. Tverberg’s theorem is 50 years old: A survey. Bulletin of the American Mathematical Society, 55(4):459-492, June 2018. URL: http://dx.doi.org/10.1090/bull/1634.
  7. Pavle V. M. Blagojević, Florian Frick, and Günter M. Ziegler. Tverberg plus constraints. Bull. Lond. Math. Soc., 46(5):953-967, 2014. Google Scholar
  8. Pavle V. M. Blagojević and Günter M. Ziegler. Beyond the Borsuk-Ulam Theorem: The Topological Tverberg Story. In: A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek (M. Loebl, J. Nešetřil, and R. Thomas, eds.), Springer, pp. 273-341, 2017. Google Scholar
  9. Jesus A. de Loera, Xavier Goaoc, Frédéric Meunier, and Nabil Mustafa. The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg. Preprint, https://arxiv.org/abs/1706.05975, 2018.
  10. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique End of Potential Line. CoRR, abs/1811.03841, 2018. URL: http://arxiv.org/abs/1811.03841.
  11. Jacob Fox and János Pach. Coloring K_k-free intersection graphs of geometric objects in the plane. European Journal of Combinatorics, 33(5):853-866, 2012. Google Scholar
  12. Florian Frick. Counterexamples to the topological Tverberg conjecture. Oberwolfach Reports, 12(1):318-321, 2015. Google Scholar
  13. Mikhail Gromov. Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry. Geom. Funct. Anal., 20(2):416-526, 2010. Google Scholar
  14. Isaac Mabillard and Uli Wagner. Eliminating Higher-Multiplicity Intersections, I. A Whitney Trick for Tverberg-Type Problems. Preprint, https://arxiv.org/abs/1508.02349, 2015. An extended abstract appeared (under the title Eliminating Tverberg points, I. An analogue of the Whitney trick) in Proc. 30th Ann. Symp. Comput. Geom., 2014, pp. 171-180.
  15. Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles, and Yannik Stein. The rainbow at the end of the line—a PPAD formulation of the colorful Carathéodory theorem with applications. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1342-1351. SIAM, 2017. Google Scholar
  16. Gary L Miller and Donald R Sheehy. Approximate centerpoints with proofs. Computational Geometry, 43(8):647-654, 2010. Google Scholar
  17. Wolfgang Mulzer and Daniel Werner. Approximating Tverberg points in linear time for any fixed dimension. Discrete &Computational Geometry, 50(2):520-535, 2013. Google Scholar
  18. Murad Özaydin. Equivariant maps for the symmetric group. Preprint, 1987. Available at URL: http://minds.wisconsin.edu/handle/1793/63829.
  19. János Pach, Natan Rubin, and Gábor Tardos. Planar point sets determine many pairwise crossing segments. In Proceedings of the 51st Annual ACM Symposium on the Theory of Computing. ACM, to appear, 2019. Google Scholar
  20. János Pach, József Solymosi, and Géza Tóth. Unavoidable configurations in complete topological graphs. Discrete &Computational Geometry, 30(2):311-320, 2003. Google Scholar
  21. Johann Radon. Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten. Mathematische Annalen, 83(1-2):113-115, 1921. Google Scholar
  22. David Rolnick and Pablo Soberón. Algorithms for Tverberg’s theorem via centerpoint theorems. Preprint, https://arxiv.org/abs/1601.03083, 2016.
  23. Arkadiy B. Skopenkov. A user’s guide to the topological Tverberg conjecture. Russian Mathematical Surveys, 73(2):323, 2018. Google Scholar
  24. Shang-Hua Teng. Points, spheres, and separators: a unified geometric approach to graph partitioning. PhD thesis, Carnegie Mellon University, 1992. Google Scholar
  25. László Fejes Tóth. Eine Kennzeichnung des Kreises. Elemente der Mathematik, 22:25-48, 1967. Google Scholar
  26. Helge Tverberg. A generalization of Radon’s theorem. Journal of the London Mathematical Society, 1(1):123-128, 1966. Google Scholar
  27. Rade T. Živaljević. Topological Methods in Discrete Geometry. In Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., chapter 21. CRC, Boca Raton, FL, 2018. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact