solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看2753次
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 查看全文>>