Is the flip graph of tetrahedralizations in 3D connected?

In the plane, any triangulation of a point set can be turned into any other by flipping diagonals one at a time. In three dimensions nobody knows whether the analogous local moves always connect all tetrahedralizations, or even whether some tetrahedralization can be stuck with no move at all.

Problem

Let $A$ be a finite set of points in $\mathbb{R}^3$ in general position (no four on a plane). A tetrahedralization of $A$ is a subdivision of the convex hull of $A$ into tetrahedra that meet face to face and whose vertices are exactly the points of $A$ . If five points of $A$ are in convex position, their convex hull has two tetrahedralizations: two tetrahedra glued along a triangle, or three tetrahedra around the segment joining the other two points. When one of these appears inside a tetrahedralization of $A$ , replacing it by the other is a 2–3 or 3–2 flip. The flip graph has the tetrahedralizations of $A$ as nodes and flips as edges.

Question. Is the flip graph connected for every point set $A$ in general position in $\mathbb{R}^3$ ? It is not even known whether it can have an isolated node.

Background

Lawson proved in 1972 that diagonal flips connect all triangulations of a planar point set [1], which underlies the incremental flipping algorithms for Delaunay triangulations. Edelsbrunner, Preparata and West (1990) and Joe (1991) asked whether the same holds in three dimensions, where the Delaunay tetrahedralization is also built by flips. The question is open even for points in convex position. A positive answer would give a local search over all tetrahedralizations; a negative one would show that flip-based methods can miss parts of the space.

What is known

The plane. The flip graph of $n$ points in general position in the plane is connected, and in fact $\lceil n/2-2\rceil$ -vertex-connected (Wagner and Welzl, 2022) [2].
Higher dimensions. Santos constructed point sets with disconnected flip graphs in dimension 6, including triangulations admitting no flip at all (2000) [3], and in dimension 5, the smallest known example having 26 points (2005). He also announced a set of 17 points in general position in $\mathbb{R}^6$ with a disconnected flip graph [4]. Dimensions 3 and 4 remain open [2], [4].
Partial results in 3D. For points in convex position, every tetrahedralization of $n$ points admits at least $n-4$ flips, so none is isolated; for general point sets there are tetrahedralizations with fewer flips than that, the smallest example having eight points [4]. For topological tetrahedralizations the answer is negative: Dougherty, Faber and Murphy built an unflippable one, but it cannot be realized with straight edges [5].
Regular triangulations, the ones obtained by projecting the lower hull of a lifted point set, are connected by flips that neither add nor remove vertices, in every dimension (Pournin and Liebling, 2007, building on Gelfand, Kapranov and Zelevinsky).

What would count as progress

A point set in general position in $\mathbb{R}^3$ , with exact coordinates, together with a tetrahedralization that has no flip, or two tetrahedralizations in different components. For small sets this can be checked by enumerating the flip graph with exact orientation tests.
Code that enumerates the flip graphs of many small point sets (for example, all order types up to some size) and reports their connectivity.
A proof of connectivity for a natural class, such as points in convex position.

References

C. L. Lawson, Transforming triangulations, Discrete Math. 3 (1972), 365–372. doi:10.1016/0012-365X(72)90093-3
U. Wagner and E. Welzl, Connectivity of triangulation flip graphs in the plane, Discrete Comput. Geom. 68 (2022), 1227–1284. doi:10.1007/s00454-022-00436-2
F. Santos, A point set whose space of triangulations is disconnected, J. Amer. Math. Soc. 13 (2000), 611–637. doi:10.1090/S0894-0347-00-00330-1
F. Santos, Geometric bistellar flips: the setting, the context and a construction, Proc. Internat. Congress of Mathematicians (Madrid, 2006), vol. III, 931–962. doi:10.4171/022-3/46, arXiv:math/0601746
R. Dougherty, V. Faber and M. Murphy, Unflippable tetrahedral complexes, Discrete Comput. Geom. 32 (2004), 309–315. doi:10.1007/s00454-004-1097-3

Source

Imported from The Open Problems Project, Problem 28, curated by Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.