Flip-graph connectivity of tetrahedralizations in three dimensions
Let $S$ be a set of $n$ points in $\mathbb{R}^3$ in general position (no four coplanar). Its flip graph has one node per tetrahedralization of $S$, and two nodes are adjacent when the tetrahedralizations differ by a 2-to-3 or 3-to-2 bistellar flip, which replaces one of the two tetrahedralizations of a convex polyhedron with five vertices by the other.
In the plane the corresponding flip graph, built from diagonal switches in convex quadrilaterals, is connected. Santos constructed point configurations in $\mathbb{R}^5$ whose triangulations are not connected by bistellar flips, and Dougherty, Faber and Murphy found unflippable topological tetrahedralizations in 3D that cannot be realized geometrically. Pournin and Liebling showed that regular triangulations in any dimension are connected by flips that neither add nor remove vertices.
Problem. Is the flip graph of every finite point set in general position in $\mathbb{R}^3$ connected?
Source: Edelsbrunner, Preparata and West (1990); Joe (1991); Problem 28 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- flip graph, tetrahedralization, The Open Problems Project
References
@article{edelsbrunner1990,
author = {Edelsbrunner, Herbert and Preparata, F. P. and West, D. B.},
title = {Tetrahedrizing Point Sets in Three Dimensions},
journal = {J. Symbolic Comput.},
volume = {10},
number = {3--4},
year = {1990},
pages = {335--347},
}
@article{joe1991,
author = {Joe, B.},
title = {Construction of Three-Dimensional {Delaunay} Triangulations Using Local Transformations},
journal = {Comput. Aided Geom. Design},
volume = {8},
number = {2},
year = {1991},
pages = {123--142},
}
@article{santos2000,
author = {Santos, Francisco},
title = {A point configuration whose space of triangulations is disconnected},
journal = {J. Amer. Math. Soc.},
volume = {13},
number = {3},
year = {2000},
pages = {611--637},
}
@article{dougherty2004,
author = {Dougherty, Randall and Faber, Vance and Murphy, Michael},
title = {Unflippable Tetrahedral Complexes},
journal = {Discrete Comput. Geom.},
volume = {32},
year = {2004},
pages = {309--315},
url = {https://doi.org/10.1007/s00454-004-1097-3},
}
@article{pournin2007,
author = {Pournin, Lionel and Liebling, Thomas M.},
title = {Constrained paths in the flip-graph of regular triangulations},
journal = {Comput. Geom. Theory Appl.},
volume = {37},
number = {2},
year = {2007},
pages = {134--140},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01079, "Flip-graph connectivity of tetrahedralizations in three dimensions", clopen.solutions.