Flip Graph Connectivity in 3D
Let be a finite set with , and assume that no four distinct points of are coplanar. A full geometric tetrahedralization of is a simplicial complex whose vertex set is exactly , whose maximal simplices are nondegenerate tetrahedra, and whose underlying space is . Let be the graph with one vertex for each such . The question is whether, for every such and every pair of full geometric tetrahedralizations of , there is a finite sequence of flips joining them; equivalently, is 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 . For the relevant five-point circuit, write its Radon partition as , where . A fixed-label flip requires and : it replaces one of the two collections below by the other, provided the collection being removed occurs in as the complete local side of the flip, leaving the rest unchanged.
Not every five-point set has a Radon partition: a partition occurs when one point lies inside the tetrahedron formed by the other four. Such a partition does not give a permitted fixed-label 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 ; hence it is not a disconnected geometric flip graph for a point set. Dougherty, Faber, and Murphy (2004)
Progress summary
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.