No-Dimensional Tverberg Theorems and Algorithms

Authors Aruni Choudhary , Wolfgang Mulzer



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.31.pdf
  • Filesize: 0.49 MB
  • 17 pages

Document Identifiers

Author Details

Aruni Choudhary
  • Institut für Informatik, Freie Universität Berlin, Takustraße 9, 14195 Berlin, Germany
Wolfgang Mulzer
  • Institut für Informatik, Freie Universität Berlin, Takustraße 9, 14195 Berlin, Germany

Acknowledgements

We would like to thank Frédéric Meunier for stimulating discussions about the Colorful Carathéodory theorem and related problems and for hosting us during a research stay at his lab. We would also like to thank Sergey Bereg for helpful comments on a previous version of this manuscript.

Cite AsGet BibTex

Aruni Choudhary and Wolfgang Mulzer. No-Dimensional Tverberg Theorems and Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.31

Abstract

Tverberg’s theorem states that for any k ≥ 2 and any set P ⊂ ℝ^d of at least (d + 1)(k - 1) + 1 points, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem lies in the complexity class PPAD ∩ PLS, but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa [SODA 2019] gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set P ⊂ ℝ^d and any k ∈ {2, … , n} in O(nd ⌈log k⌉) time a k-partition of P such that there is a ball of radius O((k/√n)diam(P)) that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, and that there are no approximation algorithms that are truly polynomial in any dimension, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria’s method [Israel Journal Math., 1992] to reduce the Tverberg problem to the Colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Graph algorithms analysis
Keywords
  • Tverberg’s theorem
  • Colorful Carathéodory Theorem
  • Tensor lifting

Metrics

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

References

  1. Karim Adiprasito, Imre Bárány, and Nabil Mustafa. Theorems of Carathéodory, Helly, and Tverberg without dimension. In Proc. 30th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 2350-2360, 2019. Google Scholar
  2. Noga Alon and Joel H. Spencer. The Probalistic method. John Wiley & Sons, 2008. Google Scholar
  3. Jorge L. Arocha, Imre Bárány, Javier Bracho, Ruy Fabila Monroy, and Luis Montejano. Very colorful theorems. Discrete Comput. Geom., 42(2):42-154, 2009. Google Scholar
  4. Imre Bárány. A generalization of Carathéodory’s theorem. Discrete Mathematics, 40(2-3):141-152, 1982. Google Scholar
  5. Imre Bárány and David G. Larman. A colored version of Tverberg’s theorem. Journal of the London Mathematical Society, s2-45(2):314-320, 1992. Google Scholar
  6. Imre Bárány and Shmuel Onn. Colourful linear programming and its relatives. Mathematics of Operations Research, 22(3):550-567, 1997. Google Scholar
  7. Pavle Blagojević, Benjamin Matschke, and Günter Ziegler. Optimal bounds for the colored Tverberg problem. Journal of the European Mathematical Society, 017(4):739-754, 2015. Google Scholar
  8. Aruni Choudhary and Wolfgang Mulzer. No-dimensional tverberg theorems and algorithms. CoRR, abs/1907.04284, 2019. URL: http://arxiv.org/abs/1907.04284.
  9. Kenneth L. Clarkson, David Eppstein, Gary L. Miller, Carl Sturtivant, and Shang-Hua Teng. Approximating center points with iterative radon points. Internat. J. Comput. Geom. Appl., 6(3):357-377, 1996. Google Scholar
  10. Aris Filos-Ratsikas and Paul W. Goldberg. The complexity of splitting necklaces and bisecting Ham sandwiches. In Proc. 51st Annu. ACM Sympos. Theory Comput. (STOC), pages 638-649, 2019. Google Scholar
  11. Sariel Har-Peled and Mitchell Jones. Journey to the center of the point set. In Proc. 35th Int. Sympos. Comput. Geom. (SoCG), pages 41:1-41:14, 2019. Google Scholar
  12. Jesús De Loera, Xavier Goaoc, Frédéric Meunier, and Nabil Mustafa. The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg. Bulletin of the American Mathematical Society, 56(3):415-511, 2019. Google Scholar
  13. Jiří Matoušek, Martin Tancer, and Uli Wagner. A geometric proof of the colored Tverberg theorem. Discrete Comput. Geom., 47(2):245-265, 2012. Google Scholar
  14. 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 Proc. 28th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 1342-1351, 2017. Google Scholar
  15. Gary L. Miller and Donald R. Sheehy. Approximate centerpoints with proofs. Comput. Geom. Theory Appl., 43(8):647-654, 2010. Google Scholar
  16. Wolfgang Mulzer and Yannik Stein. Computational aspects of the Colorful Carathéodory theorem. Discrete Comput. Geom., 60(3):720-755, 2018. Google Scholar
  17. Wolfgang Mulzer and Daniel Werner. Approximating Tverberg points in linear time for any fixed dimension. Discrete Comput. Geom., 50(2):520-535, 2013. Google Scholar
  18. Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007. Google Scholar
  19. Johann Radon. Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten. Mathematische Annalen, 83:113-115, 1921. Google Scholar
  20. Jean-Pierre Roudneff. Partitions of points into simplices with k-dimensional intersection. I. The conic Tverberg’s theorem. European Journal of Combinatorics, 22(5):733-743, 2001. Google Scholar
  21. Karanbir S. Sarkaria. Tverberg’s theorem via number fields. Israel Journal of Mathematics, 79(2-3):317-320, 1992. Google Scholar
  22. Pablo Soberón. Equal coefficients and tolerance in coloured Tverberg partitions. Combinatorica, 35(2):235-252, 2015. Google Scholar
  23. Daniel Spielman. Spectral graph theory. URL: http://www.cs.yale.edu/homes/spielman/561/.
  24. Arthur H. Stone and John W. Tukey. Generalized “Sandwich” theorems. Duke Mathematical Journal, 9(2):356-359, June 1942. Google Scholar
  25. Helge Tverberg. A generalization of Radon’s theorem. Journal of the London Mathematical Society, s1-41(1):123-128, 1966. Google Scholar
  26. Helge Tverberg. A generalization of Radon’s theorem II. Journal of the Australian Mathematical Society, 24(3):321-325, 1981. Google Scholar
  27. Helge Tverberg and Siniša T. Vrećica. On generalizations of Radon’s theorem and the Ham-sandwich theorem. European Journal of Combinatorics, 14(3):259-264, 1993. Google Scholar
  28. Rade T. Zivaljević and Siniša T. Vrećica. An extension of the Ham sandwich theorem. Bulletin of the London Mathematical Society, 22(2):183-186, 1990. Google Scholar
  29. Rade T. Zivaljević and Siniša T. Vrećica. The colored Tverberg’s problem and complexes of injective functions. Journal of Combinatorial Theory, Series A., 61:309-318, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail