2017/10/07 by Anna Lubiw, Lubiw, Anna, Zuzana Masárová +3
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1710.02741
openalex publication_date 2017/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a triangulation of a point set in the plane, a \flip deletes an\nedge e whose removal leaves a convex quadrilateral, and replaces e by the\nopposite diagonal of the quadrilateral. It is well known that any triangulation\nof a point set can be reconfigured to any other triangulation by some sequence\nof flips. We explore this question in the setting where each edge of a\ntriangulation has a label, and a flip transfers the label of the removed edge\nto the new edge.\n It is not true that every labelled triangulation of a point set can be\nreconfigured to every other labelled triangulation via a sequence of flips. We\ncharacterize when this is possible by proving the \Orbit Conjecture of\nBose, Lubiw, Pathak and Verdonschot which states that \all labels can be\nsimultaneously mapped to their destination if and only if \each label\nindividually can be mapped to its destination.\n Furthermore, we give a polynomial-time algorithm to find a sequence of flips\nto reconfigure one labelled triangulation to another, if such a sequence\nexists, and we prove an upper bound of O(n7) on the length of the flip\nsequence.\n Our proof uses the topological result that the sets of pairwise non-crossing\nedges on a planar point set form a simplicial complex that is homeomorphic to a\nhigh-dimensional ball (this follows from a result of Orden and Santos; we give\na different proof based on a shelling argument). The dual cell complex of this\nsimplicial ball, called the \flip complex, has the usual flip graph as\nits 1-skeleton. We use properties of the 2-skeleton of the flip complex to\nprove the Orbit Conjecture.\n