← All problems

Flip Graph Connectivity in 3D

36 years old · traced to

Let P⊂R3P\subset\mathbb{R}^3 be a finite set with n=∣P∣≥4n=|P|\geq 4, and assume that no four distinct points of PP are coplanar. A full geometric tetrahedralization of PP is a simplicial complex TT whose vertex set is exactly PP, whose maximal simplices are nondegenerate tetrahedra, and whose underlying space is conv⁡(P)\operatorname{conv}(P). Let F(P)\mathcal{F}(P) be the graph with one vertex for each such TT. The question is whether, for every such PP and every pair T,T′T,T' of full geometric tetrahedralizations of PP, there is a finite sequence of flips joining them; equivalently, is F(P)\mathcal{F}(P) connected? Open Problems Project, Problem 28 Flip Graphs for Eight Points in Three Dimensions Are Connected (2026 preprint)

A permitted flip replaces two tetrahedra by three, or three by two, on the same five-point set QQ. For the relevant five-point circuit, write its Radon partition as Q=A∪˙BQ=A\mathbin{\dot\cup}B, where conv⁡(A)∩conv⁡(B)≠∅\operatorname{conv}(A)\cap\operatorname{conv}(B)\neq\varnothing. A fixed-label 2↔32\leftrightarrow3 flip requires ∣A∣=2|A|=2 and ∣B∣=3|B|=3: it replaces one of the two collections below by the other, provided the collection being removed occurs in TT as the complete local side of the flip, leaving the rest unchanged.

{conv⁡(Q∖{a}):a∈A}⟷{conv⁡(Q∖{b}):b∈B}.\{\operatorname{conv}(Q\setminus\{a\}):a\in A\} \quad\longleftrightarrow\quad \{\operatorname{conv}(Q\setminus\{b\}):b\in B\}.

Not every five-point set has a 2∣32|3 Radon partition: a 1∣41|4 partition occurs when one point lies inside the tetrahedron formed by the other four. Such a partition does not give a permitted fixed-label 2↔32\leftrightarrow3 flip. Flip Graphs for Eight Points in Three Dimensions Are Connected (2026 preprint)

Background

The two-dimensional analogue is connected: flips switch the diagonal of a convex quadrilateral, and paths in the flip graph can be used in algorithms that move toward a Delaunay triangulation. The three-dimensional connectivity problem was raised in work by Edelsbrunner, Preparata, and West and by Joe, and was highlighted as an open problem in Mitchell and O’Rourke’s 2001 computational-geometry column. The local move is more restrictive geometrically: it is a replacement across a five-point circuit, not an arbitrary change between tetrahedralizations. Open Problems Project, Problem 28 Mitchell and O’Rourke (2001)

Abstract bistellar connectivity is related but does not answer the geometric question. Dougherty, Faber, and Murphy exhibited a 16-vertex tetrahedralization of the 3-sphere that admits no topological bistellar move other than vertex insertion. They also showed that this complex, and others with the relevant properties, cannot be realized geometrically in R3\mathbb{R}^3; hence it is not a disconnected geometric flip graph for a point set. Dougherty, Faber, and Murphy (2004)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.