Flip Paths Between Lattice Triangulations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914645384626176 |
|---|---|
| author | Sims, William Sitharam, Meera |
| author_facet | Sims, William Sitharam, Meera |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2008_11292 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Flip Paths Between Lattice Triangulations Sims, William Sitharam, Meera Computational Geometry Discrete Mathematics 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. |
| title | Flip Paths Between Lattice Triangulations |
| topic | Computational Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/2008.11292 |