Flip Paths Between Lattice Triangulations

Diagonal flip paths between triangulations have been studied in the combinatorial setting for nearly a century. One application of flip paths to Euclidean distance geometry and Moebius geometry is a recent, simple, constructive proof by Connelly and Gortler of the Koebe-Andreev-Thurston circle packing theorem that relies on the existence of a flip path between any two triangulation graphs. More generally, length and other structural quantities on minimum (length) flip paths are metrics on the space of triangulations. In the geometric setting, finding a minimum flip path between two triangulations is NP-complete. However, for two lattice triangulations, used to model electron spin systems, Eppstein and Caputo et al. gave algorithms running in $O\left(n^2\right)$ time, where $n$ is the number of points in the point-set. Their algorithms apply to constrained flip paths that ensure a set of \emph{constraint} edges are present in every triangulation along the path. We reformulate the problem and provide an algorithm that runs in $O\left(n^{\frac{3}{2}}\right)$ time. In fact, for a large, natural class of inputs, the bound is tight, i.e., our algorithm runs in time linear in the length of this output flip path. Our results rely on structural elucidation of minimum flip paths. Specifically, for any two lattice triangulations, we use Farey sequences to construct a partially-ordered sets of flips, called a minimum flip \emph{plan}, whose linear-orderings are minimum flip paths between them. To prove this, we characterize a minimum flip plan that starts from an equilateral lattice triangulation - i.e., a lattice triangulation whose edges are all unit-length - and \emph{forces a point-pair to become an edge}. To the best of our knowledge, our results are the first to exploit Farey sequences for elucidating the structure of flip paths between lattice triangulations.