Academic Journals Database
Disseminating quality controlled scientific knowledge

Happy Endings for Flip Graphs

ADD TO MY LIST
 
Author(s): David Eppstein

Journal: Journal of Computational Geometry
ISSN 1920-180X

Volume: 1;
Issue: 1;
Start page: 3;
Date: 2010;
Original page

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.

Tango Jona
Tangokurs Rapperswil-Jona

    
RPA Switzerland

Robotic Process Automation Switzerland