论文标题
晶格三角形之间的翻转路径
Flip Paths Between Lattice Triangulations
论文作者
论文摘要
我们提出了一个$ O（n^{\ frac {3} {2}}）$ - \ emph {lattice}三角形的\ emph {最短（对角线）翻转路径问题}的时间算法。对于大型天然的输入类别，我们的界限很紧，从某种意义上说，我们的算法在输出翻转路径中的翻转数量中线性运行。我们的结果取决于最短翻转路径的独立有趣的结构阐明，作为独特的部分有序集的线性顺序，称为\ emph {最小翻转计划}，这是由基本数字理论中的farey序列的新颖使用构成的。近一个世纪以来，已经在组合环境中研究了一般（不一定是晶格）三角剖分之间的翻转路径。在欧几里得的几何环境中，在两个三角形之间找到最短的翻转路径是NP完整的。但是，对于被研究为旋转系统的晶格三角剖分，已知$ o \ weft（n^2 \右）$ - 时间算法可以找到最短的翻转路径。这些算法以及我们的算法适用于\ emph {约束}翻转路径，这些路径可确保沿路径的每个三角剖分中都存在一组\ emph {约束}边缘。讨论了确定同时变形边缘的含义，即讨论了在晶格三角形之间找到最佳的同时翻转路径，并讨论了计数晶格三角剖分。
We present a $O(n^{\frac{3}{2}})$-time algorithm for the \emph{shortest (diagonal) flip path problem} for \emph{lattice} triangulations with $n$ points, improving over previous $O(n^2)$-time algorithms. For a large, natural class of inputs, our bound is tight in the sense that our algorithm runs in time linear in the number of flips in the output flip path. Our results rely on an independently interesting structural elucidation of shortest flip paths as the linear orderings of a unique partially ordered set, called a \emph{minimum flip plan}, constructed by a novel use of Farey sequences from elementary number theory. Flip paths between general (not necessarily lattice) triangulations have been studied in the combinatorial setting for nearly a century. In the Euclidean geometric setting, finding a shortest flip path between two triangulations is NP-complete. However, for lattice triangulations, which are studied as spin systems, there are known $O\left(n^2\right)$-time algorithms to find shortest flip paths. These algorithms, as well as ours, apply to \emph{constrained} flip paths that ensure a set of \emph{constraint} edges are present in every triangulation along the path. Implications for determining simultaneously flippable edges, i.e. finding optimal simultaneous flip paths between lattice triangulations, and for counting lattice triangulations are discussed.
