3?
Given a set of n points in
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
3, a 5-vertex convex polyhedron is ``flipped'' between two
of its tetrahedralizations.
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
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
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).