next up previous
Next: Problem 29: Hamiltonian Tetrahedralizations Up: The Open Problems Project Previous: Problem 27: Hexahedral Meshing

Problem 28: Flip Graph Connectivity in 3D

Is the flip graph connected for general-position points in $ \mathbb {R}$3? Given a set of n points in $ \mathbb {R}$3, the flip graph has a node for each tetrahedralization of the set. Two nodes are connected by an arc if there is a 2-to-3 or 3-to-2 ``bistellar flip'' of tetrahedra between the two simplicial complexes. In the plane, the flips correspond to convex quadrilateral diagonal switches; in $ \mathbb {R}$3, a 5-vertex convex polyhedron is ``flipped'' between two of its tetrahedralizations.
Partial and Related Results
In $ \mathbb {R}$2 the flip graph is connected, providing a basis for algorithms to iterate toward the Delaunay triangulation. A decade ago, several [EPW90,Joe91] asked whether the same holds in $ \mathbb {R}$3 (when no four points are coplanar), but the question remains unresolved. It is not even known whether the flip graph might contain an isolated node. Settled in the negative for points in $ \mathbb {R}$5 by Santos [San00], by constructing polytopes with a space of triangulations not connected via bistellar flips. Settled in the negative for topological tetrahedralizations in 3D, but the constructed tetrahedralization cannot be realized geometrically [DFM04].

Settled in the positive for flip graphs of regular triangulations in any dimension in [PL07], based on earlier work of Gelfand, Kapranov and Zelevinsky. The result in [PL07] connects by flips that neither remove nor add vertices (i.e., 2-to-3 or 3-to-2 flips in 3D), whereas the earlier work by Gelfand et al. permits all flips (e.g., 1-to-4 and 4-to-1 flips in 3D).

Related Open Problems
Problem 27
triangulations; Delaunay triangulations
Entry Revision History
J. O'Rourke, 2 Aug. 2001; 7 Dec. 2001 (thanks to F. Santos); E. Demaine, 10 Dec. 2001; J. O'Rourke, 18 Feb. 2002 (thanks to D. Eppstein); E. Demaine, 2 Aug. 2004 (thanks to M. Murphy); J. O'Rourke, 20 Aug 2006. J. O'Rourke, 22 Dec 2008 (thanks to L. Pournin).


Randall Dougherty, Vance Faber, and Michael Murphy.
Unflippable tetrahedral complexes.
Discrete Comput. Geom., 32:309-315, 2004.

Herbert Edelsbrunner, F. P. Preparata, and D. B. West.
Tetrahedrizing point sets in three dimensions.
J. Symbolic Comput., 10(3-4):335-347, 1990.

B. Joe.
Construction of three-dimensional Delaunay triangulations using local transformations.
Comput. Aided Geom. Design, 8(2):123-142, May 1991.

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573-582, 2001.
Also in SIGACT News 32(3):63-72 (2001), Issue 120.

Lionel Pournin and Thomas M. Liebling.
Constrained paths in the flip-graph of regular triangulations.
Comput. Geom. Theory Appl., 37(2):134-140, 2007.

Francisco Santos.
A point configuration whose space of triangulations is disconnected.
J. Amer. Math. Soc., 13(3):611-637, 2000.

next up previous
Next: Problem 29: Hamiltonian Tetrahedralizations Up: The Open Problems Project Previous: Problem 27: Hexahedral Meshing
The Open Problems Project - September 19, 2017