Flip Paths Between Lattice Triangulations
This talk has two primary motivations from the physical sciences: (i) to make progress on open problems on Glauber dynamics for electron spin systems and (ii) to present a new computational model based on discrete geometry for crack propagation in crystalline structures, such as graphene. Both goals require a deeper understanding of the structure of (diagonal) flip paths between lattice triangulations, which are integral to the above models. We present an O(n^(3/2))-time algorithm for the shortest flip path problem for 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 length (number of flips) of 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 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, the problem of finding a shortest flip path between two triangulations is NP-complete. However, for lattice triangulations, there are known O(n^2)-time algorithms for shortest flip paths. These algorithms, as well as ours, apply to constrained flip paths that ensure a set of constraint edges are present in every triangulation along the path. Implications for Goals (i) and (ii), as well as for other open problems of independent mathematical/algorithmic interest are discussed.