Open AccessHappy endings for flip graphs
Author(s) -
David Eppstein
Publication year - 2007
Publication title -
journal of computational geometry (carleton university)
Language(s) - English
Resource type - Conference proceedings
DOI - 10.1145/1247069.1247084
Subject(s) - combinatorics , pentagon , regular polygon , hypercube , point (geometry) , mathematics , set (abstract data type) , discrete mathematics , computer science , topology (electrical circuits) , geometry , programming language
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 of this type 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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom