Hamiltonian tetrahedralizations of convex polytopes
The dual graph of a tetrahedralization has one node per tetrahedron, two nodes being adjacent when their tetrahedra share a triangular face. A tetrahedralization is Hamiltonian if its dual graph has a Hamiltonian path.
Arkin, Held, Mitchell and Skiena showed that every convex polygon has a Hamiltonian triangulation while some nonconvex polygons do not. Chin, Ding and Wang gave convex polytopes whose pulling tetrahedralization, coning one vertex to all the others, is not Hamiltonian. Escalona, Fabila-Monroy and Urrutia showed that every set of at most $20$ points admits a Hamiltonian tetrahedralization, and gave an $O(n^{3/2})$-time algorithm that finds one for $n$ points after adding $O(n)$ Steiner points.
Problem. Does every convex polytope in $\mathbb{R}^3$ admit a decomposition into tetrahedra whose dual graph has a Hamiltonian path?
Source: Arkin, Held, Mitchell and Skiena (1996); Problem 29 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- dual graph, Hamiltonian path, tetrahedralization, The Open Problems Project
References
@article{arkin1996,
author = {Arkin, Esther M. and Held, Martin and Mitchell, Joseph S. B. and Skiena, Steven S.},
title = {Hamiltonian Triangulations for Fast Rendering},
journal = {Visual Comput.},
volume = {12},
number = {9},
year = {1996},
pages = {429--444},
}
@inproceedings{chin2005,
author = {Chin, Francis and Ding, Qing-Huai and Wang, Cao An},
title = {On {Hamiltonian} Tetrahedralizations Of Convex Polyhedra},
booktitle = {The Fifth International Symposium (ISORA 05)},
editor = {Zhang, Xiang-Sun and Liu, De-Gang and Wu, Ling-Yun},
series = {Operations Research and its Applications, Lecture Notes in Operations Research},
volume = {5},
publisher = {World Publishing Corporation},
year = {2005},
pages = {206--216},
url = {http://www.cs.hku.hk/~chin/paper/ISORA05.ps},
}
@inproceedings{escalona2007,
author = {Escalona, Francisco and Fabila-Monroy, Ruy and Urrutia, Jorge},
title = {Hamiltonian Tetrahedralizations with Steiner Points},
booktitle = {Abstracts 23rd European Workshop on Computational Geometry},
year = {2007},
pages = {50--53},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01080, "Hamiltonian tetrahedralizations of convex polytopes", clopen.solutions.