  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.
