Happy endings for flip graphs

David Eppstein

Abstract


We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets with no empty pentagon include intersections of lattices with convex sets, points on two lines, and several other infinite families. As a consequence, flip distance in such point sets can be computed efficiently.

Full Text: PDF

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

ISSN: 1920-180X