Document Open Access Logo

A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations

Authors Anna Lubiw, Zuzana Masárová, Uli Wagner

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.49.pdf
  • Filesize: 0.67 MB
  • 15 pages

Document Identifiers

Author Details

Anna Lubiw
Zuzana Masárová
Uli Wagner

Cite As Get BibTex

Anna Lubiw, Zuzana Masárová, and Uli Wagner. A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.49

Abstract

Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of O(n^7) on the length of the flip sequence.  

Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.

Subject Classification

Keywords
  • triangulations
  • reconfiguration
  • flip
  • constrained triangulations
  • Delaunay triangulation
  • shellability
  • piecewise linear balls

Metrics

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

References

  1. Oswin Aichholzer, Wolfgang Mulzer, and Alexander Pilz. Flip distance between triangulations of a simple polygon is NP-complete. Discrete &Computational Geometry, 54(2):368-389, 2015. URL: http://dx.doi.org/10.1007/s00454-015-9709-7.
  2. Gabriela Araujo-Pardo, Isabel Hubard, Deborah Oliveros, and Egon Schulte. Colorful associahedra and cyclohedra. Journal of Combinatorial Theory, Series A, 129:122-141, 2015. URL: http://dx.doi.org/10.1016/j.jcta.2014.09.001.
  3. Marshall Bern and David Eppstein. Mesh generation and optimal triangulation. In Ding-Zhu Du and Frank Hwang, editors, Computing in Euclidean geometry, volume 1 of Lecture Notes Series on Computing, pages 23-90. World Scientific, 1992. URL: http://dx.doi.org/10.1142/9789814355858_0002.
  4. R. H. Bing. Some aspects of the topology of 3-manifolds related to the Poincaré conjecture. In Lectures on modern mathematics, Vol. II, pages 93-128. Wiley, New York, 1964. Google Scholar
  5. Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler. Oriented Matroids, volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2nd edition, 1999. URL: http://dx.doi.org/10.1017/CBO9780511586507.
  6. Prosenjit Bose and Ferran Hurtado. Flips in planar graphs. Computational Geometry Theory and Applications, 42(1):60-80, 2009. URL: http://dx.doi.org/10.1016/j.comgeo.2008.04.001.
  7. Prosenjit Bose, Anna Lubiw, Vinayak Pathak, and Sander Verdonschot. Flipping edge-labelled triangulations. arXiv:1310.1166, 2013. To appear in Computational Geometry. URL: http://arxiv.org/abs/1310.1166.
  8. Prosenjit Bose and Sander Verdonschot. Flips in edge-labelled pseudo-triangulations. Computational Geometry, 60:45-54, 2017. Google Scholar
  9. Javier Cano, José-Miguel Díaz-Báñez, Clemens Huemer, and Jorge Urrutia. The edge rotation graph. Graphs and Combinatorics, 29(5):1207-1219, 2013. URL: http://dx.doi.org/10.1007/s00373-012-1201-z.
  10. Gopal Danaraj and Victor Klee. Shellings of spheres and polytopes. Duke Mathematical Journal, 41(2):443-451, 1974. Google Scholar
  11. Satyan L. Devadoss and Joseph O'Rourke. Discrete and Computational Geometry. Princeton University Press, 2011. Google Scholar
  12. N. Dyn, I. Goren, and S. Rippa. Transforming triangulations in polygonal domains. Computer Aided Geometric Design, 10:531-536, 1993. Google Scholar
  13. Herbert Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge University Press, Cambridge, 2001. URL: http://dx.doi.org/10.1017/CBO9780511530067.
  14. David Eppstein. Happy endings for flip graphs. Journal of Computational Geometry, 1(1):3-28, 2010. URL: http://dx.doi.org/10.20382/jocg.v1i1a2.
  15. J. F. P. Hudson. Piecewise Linear Topology. W. A. Benjamin, Inc., New York-Amsterdam, 1969. Google Scholar
  16. Ferran Hurtado, Marc Noy, and Jorge Urrutia. Flipping edges in triangulations. Discrete &Computational Geometry, 22(3):333-346, 1999. URL: http://dx.doi.org/10.1007/PL00009464.
  17. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theoretical Computer Science, 412(12-14):1054-1065, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2010.12.005.
  18. Charles L. Lawson. Transforming triangulations. Discrete Mathematics, 3(4):365-372, 1972. Google Scholar
  19. Charles L. Lawson. Software for C¹ surface interpolation. In Mathematical Software III, pages 161-194. Academic Press, New York, 1977. Google Scholar
  20. Anna Lubiw and Vinayak Pathak. Flip distance between two triangulations of a point set is NP-complete. Computational Geometry, 49:17-23, 2015. URL: http://dx.doi.org/10.1016/j.comgeo.2014.11.001.
  21. Anna Lubiw and Vinayak Pathak. Reconfiguring ordered bases of a matroid. arXiv:1612.00958, 2016. Google Scholar
  22. Michael Molloy, Bruce Reed, and William Steiger. On the mixing rate of the triangulation walk. In DIMACS-AMS volume on Randomization Methods in Algorithm Design, volume 43 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 179-190. AMS, 1999. Google Scholar
  23. James R. Munkres. Elements of Algebraic Topology. Addison-Wesley Publishing Company, Menlo Park, CA, 1984. Google Scholar
  24. David Orden and Francisco Santos. The polytope of non-crossing graphs on a planar point set. Discrete &Computational Geometry, 33(2):275-305, 2005. URL: http://dx.doi.org/10.1007/s00454-004-1143-1.
  25. Alexander Pilz. Flip distance between triangulations of a planar point set is APX-hard. Computational Geometry, 47(5):589-604, 2014. URL: http://dx.doi.org/10.1016/j.comgeo.2014.01.001.
  26. Lionel Pournin. The diameter of associahedra. Advances in Mathematics, 259:13-42, 2014. URL: http://dx.doi.org/10.1016/j.aim.2014.02.035.
  27. Herbert Seifert and William Threlfall. A Textbook of Topology, volume 89 of Pure and Applied Mathematics. Academic Press, 1980. Google Scholar
  28. Daniel D. Sleator, Robert E. Tarjan, and William P. Thurston. Rotation distance, triangulations, and hyperbolic geometry. Journal of the American Mathematical Society, 1(3):647-681, 1988. URL: http://dx.doi.org/10.2307/1990951.
  29. John Stillwell. Classical Topology and Combinatorial Group Theory, volume 72 of Graduate Texts in Mathematics. Springer-Verlag, 2nd edition, 1993. URL: http://dx.doi.org/10.1007/978-1-4612-4372-4.
  30. Jan van den Heuvel. The complexity of change. Surveys in Combinatorics, 409:127-160, 2013. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact