Problem 28: Flip Graph Connectivity in 3D

Statement

Is the flip graph connected for general-position points in $\mathbb {R}$³? Given a set of n points in $\mathbb {R}$³, 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}$<sup>3</sup>, a 5-vertex convex polyhedron is ``flipped'' between two of its tetrahedralizations.

Origin

[EPW90,Joe91]

Status/Conjectures

Open.

Partial and Related Results

In $\mathbb {R}$² 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}$³ (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}$⁵ 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].

Related Open Problems

Problem 27

Appearances

[MO01]

Categories

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.

Bibliography

DFM04

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

EPW90

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

Joe91

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

MO01

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.

San00

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