Next: Problem 29: Hamiltonian Tetrahedralizations
Previous: Problem 27: Hexahedral Meshing
Is the flip graph connected for general-position points in \R^3? Given a set of n points in \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 \R^3, a 5-vertex convex polyhedron is “flipped” between two of its tetrahedralizations.
Open.
In \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 \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 \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).
triangulations; Delaunay triangulations
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.