The problem of finding a diagonal flip path between two triangulations has been studied for nearly a century in the combinatorial (topological) setting and for decades in the geometric setting . In the geometric setting, finding a diagonal flip path between two triangulations that minimizes the number of diagonal flips over all such paths is NP-complete. However, when restricted to lattice triangulations- i. e. triangulations of a finite subset of the integer lattice, or an affine transformation of this lattice, bounded by a simple, closed polygon with lattice points as vertices - the problem has a polynomial time algorithm. Lattice triangulations have been studied for their uses in discriminant theory, Hilbert's 16th problem, toric varieties, quantum spin systems, and material science\left(\right)  . Our first main result shows that there is a polynomial-time computable, unique partially-ordered set of diagonal flips such that there is a bijection between valid linear-orderings of this set and minimum diagonal flip paths between two lattice triangulations . This provides an alternative proof of the previously known result, as well as new structural insights into these diagonal flip paths\left({2}}}\right)  . Our second main result characterizes pairs of triangulations , containing sets of edges E and E ' respectively, such that the minimum diagonal flip path between them contains the minimum number of diagonal flips over all minimum diagonal flip paths between pairs of triangulations , containing sets of edges E and E' respectively. Remarkably, all of our results are derived from a simple relationship between edges in triangulations and Farey sequences .
The problem of finding a diagonal flip path between two triangulations has been studied for nearly a century . In the geometric setting, finding a flip path between two triangulations containing the minimum number of flips is NP-complete. However, for minimum flip paths between lattice triangulations, 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. Eppstein proved this result for lattice point-sets bounded by convex polygons. Caputo et al. extended this result to the cases of non-convex bounding polygons and constrained flip paths that preserve a set of edges. In fact, Eppstein's approach readily extends to both cases . Our first result shows that there is a unique, partially-ordered set of flips whose valid linear-orderings are exactly the constrained, minimum flip paths between two lattice triangulations , leading to an algorithm to compute such a minimum flip path in O\left(n^{\frac{3{2}}}\right) time. As a further improvement over previous results, in many natural cases, our algorithm runs in time linear in the length of the minimum flip path . Our second result characterizes pairs of triangulations T and T' that contain given sets of edges G and G ' respectively, and attain the minimum flip path between each other, where the minimum is taken over such pairs of triangulations . Finally, we demonstrate how our results can model crack propagation in crystalline materials caused by Stone-Wales defects. Notably, the above results follow from simple number-theoretic and geometric concepts .
R
flip
flip
D
in the combinatorial (topological) setting and for decades in the geometric setting
D
diagonal
R
that minimizes the number of diagonal flips over all such paths
containing the minimum number of flips
R
when restricted to lattice triangulations- i. e. triangulations of a finite subset of the integer lattice, or an affine transformation of this lattice, bounded by a simple, closed polygon with lattice points as vertices - the problem has a polynomial time algorithm. Lattice triangulations have been studied for their uses in discriminant theory, Hilbert's 16th problem, toric varieties, quantum spin systems, and material science
for minimum flip paths between lattice triangulations, Eppstein and Caputo et al. gave algorithms running in O
A
n^2
A
time, where n is the number of points in the point-set. Eppstein proved this result for lattice point-sets bounded by convex polygons. Caputo et al. extended this result to the cases of non-convex bounding polygons and constrained flip paths that preserve a set of edges. In fact, Eppstein's approach readily extends to both cases
D
main
R
polynomial-time computable, unique
unique,
R
diagonal flips such that there is a bijection between
flips whose
R
of this set and minimum diagonal
are exactly the constrained, minimum
R
. This provides an alternative proof of the previously known result, as well as new structural insights into these diagonal flip paths
, leading to an algorithm to compute such a minimum flip path in O
A
n^{\frac{3
A
time. As a further improvement over previous results, in many natural cases, our algorithm runs in time linear in the length of the minimum flip path
D
main
R
, containing
T and T' that contain given
R
E and E
G and G
R
such that the minimum diagonal
and attain the minimum
R
them contains the minimum number of diagonal flips over all minimum diagonal flip paths between
each other, where the minimum is taken over such
R
, containing sets of edges E and E' respectively. Remarkably, all of our results are derived from a simple relationship between edges in triangulations and Farey sequences
. Finally, we demonstrate how our results can model crack propagation in crystalline materials caused by Stone-Wales defects. Notably, the above results follow from simple number-theoretic and geometric concepts