solidot新版网站常见问题,请点击这里查看。

A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations. (arXiv:1710.02741v1 [cs.CG])

来源于:arXiv
Given a triangulation of a point set in the plane, a \emph{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. We characterize when this is possible by proving the \emph{Orbit Conjecture} of Bose, Lubiw, Pathak and Verdonschot which states that \emph{all} labels can be simultaneously mapped to their destination if and only if \emph{each} label individually can be mapped to its destination. Furthermore, we give a polynomial-time algorithm to find a sequence of flips to reconfigure 查看全文>>