Document Open Access Logo

Convex Hulls of Random Order Types

Authors Xavier Goaoc, Emo Welzl

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.49.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Author Details

Xavier Goaoc
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Emo Welzl
  • Department of Computer Science, ETH Zürich, Switzerland

Funding

  • Goaoc, Xavier: Supported by grant ANR-17-CE40-0017 of the French National Research Agency (ANR project ASPAG) and Institut Universitaire de France.
  • Welzl, Emo: Supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681.

Acknowledgements

This research started at the Banff Workshop "Helly and Tverberg Type Theorems", October 6-11, 2019, at the Casa Matemática Oaxaca (CMO), Mexico. The authors thank Boris Aronov for helpful discussions, Gernot Stroth for help on the group theoretic aspects of the paper, and Pierre Calka for help on questions involving probabilistic geometry.

Cite AsGet BibTex

Xavier Goaoc and Emo Welzl. Convex Hulls of Random Order Types. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.49

Abstract

We establish the following two main results on order types of points in general position in the plane (realizable simple planar order types, realizable uniform acyclic oriented matroids of rank 3): (a) The number of extreme points in an n-point order type, chosen uniformly at random from all such order types, is on average 4+o(1). For labeled order types, this number has average 4-8/(n^2 - n +2) and variance at most 3. (b) The (labeled) order types read off a set of n points sampled independently from the uniform measure on a convex planar domain, smooth or polygonal, or from a Gaussian distribution are concentrated, i.e., such sampling typically encounters only a vanishingly small fraction of all order types of the given size. Result (a) generalizes to arbitrary dimension d for labeled order types with the average number of extreme points 2d+o(1) and constant variance. We also discuss to what extent our methods generalize to the abstract setting of uniform acyclic oriented matroids. Moreover, our methods allow to show the following relative of the Erdős-Szekeres theorem: for any fixed k, as n → ∞, a proportion 1 - O(1/n) of the n-point simple order types contain a triangle enclosing a convex k-chain over an edge. For the unlabeled case in (a), we prove that for any antipodal, finite subset of the 2-dimensional sphere, the group of orientation preserving bijections is cyclic, dihedral or one of A₄, S₄ or A₅ (and each case is possible). These are the finite subgroups of SO(3) and our proof follows the lines of their characterization by Felix Klein.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • order type
  • oriented matroid
  • Sylvester’s Four-Point Problem
  • random convex hull
  • projective plane
  • excluded pattern
  • Hadwiger’s transversal theorem
  • hairy ball theorem

Metrics

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

Related Versions

References

  1. Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser. Enumerating order types for small point sets with applications. Order, 19(3):265-281, 2002. URL: https://doi.org/10.1023/A:1021231927255.
  2. Oswin Aichholzer and Hannes Krasser. Abstract order type extension and new results on the rectilinear crossing number. Computational Geometry, 36(1):2-15, 2007. Special Issue on the 21st European Workshop on Computational Geometry. URL: https://doi.org/10.1016/j.comgeo.2005.07.005.
  3. Noga Alon. The number of polytopes, configurations and real matroids. Mathematika, 33(1):62-71, 1986. Google Scholar
  4. Greg Aloupis, John Iacono, Stefan Langerman, Özgür Özkan, and Stefanie Wuhrer. The complexity of order type isomorphism. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 405-415. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.30.
  5. Imre Bárány, Matthieu Fradelizi, Xavier Goaoc, Alfredo Hubard, and Günter Rote. Random polytopes and the wet part for arbitrary probability distributions. arXiv preprint, 2019. URL: http://arxiv.org/abs/1902.06519.
  6. Imre Bárány and David G Larman. Convex bodies, economic cap coverings, random polytopes. Mathematika, 35(2):274-291, 1988. Google Scholar
  7. Yuliy M Baryshnikov and Richard A Vitale. Regular simplices and Gaussian samples. Discrete & Computational Geometry, 11(2):141-147, 1994. Google Scholar
  8. Marshall W. Bern, David Eppstein, Paul E. Plassmann, and F. Frances Yao. Horizon theorems for lines and polygons. In Jacob E. Goodman, Richard Pollack, and William Steiger, editors, Discrete and Computational Geometry: Papers from the DIMACS Special Year, volume 6 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 45-66. DIMACS/AMS, 1990. URL: https://doi.org/10.1090/dimacs/006/03.
  9. Anders Bjorner, Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Gunter M Ziegler. Oriented matroids. Number 46 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1999 . Google Scholar
  10. Jean Cardinal, Ruy Fabila-Monroy, and Carlos Hidalgo-Toscano. Chirotopes of random points in space are realizable on a small integer grid. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.08062.
  11. Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher, Patrick Schnider, Raphael Steiner, and Pavel Valtr. On the average complexity of the k-level. CoRR, abs/1911.02408, 2019. URL: http://arxiv.org/abs/1911.02408.
  12. Olivier Devillers, Philippe Duchon, Marc Glisse, and Xavier Goaoc. On order types of random point sets, 2018. URL: http://arxiv.org/abs/1812.08525v2.
  13. David Eppstein. Forbidden configurations in discrete geometry. Cambridge University Press, 2018. Google Scholar
  14. Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio mathematica, 2:463-470, 1935. Google Scholar
  15. Ruy Fabila-Monroy and Clemens Huemer. Order types of random point sets can be realized with small integer coordinates. In XVII Spanish Meeting on Computational Geometry: book of abstracts, Alicante, June 26-28, pages 73-76, 2017. Google Scholar
  16. Tobias Gerken. Empty convex hexagons in planar point sets. Discrete & Computational Geometry, 39(1-3):239-272, 2008. Google Scholar
  17. Xavier Goaoc and Emo Welzl. Convex hulls of random order types. CoRR, abs/2003.08456, 2020. URL: https://arxiv.org/abs/2003.08456.
  18. Jacob E Goodman and Richard Pollack. Multidimensional sorting. SIAM Journal on Computing, 12(3):484-507, 1983. Google Scholar
  19. Jacob E Goodman and Richard Pollack. Upper bounds for configurations and polytopes inr d. Discrete & Computational Geometry, 1(3):219-227, 1986. Google Scholar
  20. Jacob E Goodman, Richard Pollack, and Bernd Sturmfels. The intrinsic spread of a configuration in ℝ^d. Journal of the American Mathematical Society, pages 639-651, 1990. Google Scholar
  21. Jie Han, Yoshiharu Kohayakawa, Marcelo T Sales, and Henrique Stagni. Extremal and probabilistic results for order types. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 426-435. SIAM, 2019. Google Scholar
  22. Sariel Har-Peled. On the expected complexity of random convex hulls. CoRR, abs/1111.5340, 2011. URL: http://arxiv.org/abs/1111.5340.
  23. Gyula Károlyi and Jozsef Solymosi. Erdős-Szekeres theorem with forbidden order types. Journal of Combinatorial Theory, Series A, 113(3):455-465, 2006. Google Scholar
  24. Gyula Károlyi and Géza Tóth. Erdős-Szekeres theorem for point sets with forbidden subconfigurations. Discrete & Computational Geometry, 48(2):441-452, 2012. Google Scholar
  25. Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap. Classroom examples of robustness problems in geometric computations. Computational Geometry, 40(1):61-78, 2008. Google Scholar
  26. Donald Ervin Knuth. Axioms and hulls, volume 606. Springer, 1992. Google Scholar
  27. Adam Marcus and Gábor Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. Journal of Combinatorial Theory, Series A, 107(1):153-160, 2004. Google Scholar
  28. Hiroyuki Miyata. On symmetry groups of oriented matroids, 2013. URL: http://arxiv.org/abs/1301.6451.
  29. Nicolai E. Mnëv. The universality theorem on the oriented matroid stratification of the space of real matrices. In Jacob E. Goodman, Richard Pollack, and William Steiger, editors, Discrete and Computational Geometry: Papers from the DIMACS Special Year, volume 6 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 237-244. DIMACS/AMS, 1990. URL: https://doi.org/10.1090/dimacs/006/16.
  30. Jaroslav Nešetřil and Pavel Valtr. A Ramsey property of order types. Journal of Combinatorial Theory, Series A, 81(1):88-107, 1998. Google Scholar
  31. Alfredo García Olaverri, Marc Noy, and Javier Tejel. Lower bounds on the number of crossing-free subgraphs of K_N. Comput. Geom., 16(4):211-221, 2000. URL: https://doi.org/10.1016/S0925-7721(00)00010-9.
  32. Mark Overmars. Finding sets of points without empty convex 6-gons. Discrete & Computational Geometry, 29(1):153-158, 2002. Google Scholar
  33. M. Reitzner. Random polytopes. In Wilfrid S. Kendall and Ilya Molchanov, editors, New Perspectives in Stochastic Geometry, chapter 2, pages 45-75. Oxford University Press, 2009. Google Scholar
  34. Alfréd Rényi and Rolf Sulanke. Über die konvexe Hülle von n zufällig gewählten Punkten. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 2(1):75-84, 1963. Google Scholar
  35. Alfréd Rényi and Rolf Sulanke. Über die konvexe Hülle von n zufällig gewählten Punkten. II. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 3(2):138-147, 1964. Google Scholar
  36. Marcus Schaefer. Complexity of some geometric and topological problems. In David Eppstein and Emden R. Gansner, editors, Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009. Revised Papers, volume 5849 of Lecture Notes in Computer Science, pages 334-344. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-11805-0_32.
  37. Peter Shor. Stretchability of pseudolines is NP-hard. Applied Geometry and Discrete Mathematics-The Victor Klee Festschrift, 1991. Google Scholar
  38. The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 4.14 edition, 2019. URL: https://doc.cgal.org/4.14/Manual/packages.html.
  39. Ivor van der Hoog, Tillmann Miltzow, and Martijn van Schaik. Smoothed analysis of order types. arXiv preprint, 2019. URL: http://arxiv.org/abs/1907.04645.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact