next up previous
Next: Problem 30: Thrackles Up: The Open Problems Project Previous: Problem 28: Flip Graph


Problem 29: Hamiltonian Tetrahedralizations

Statement
Can every convex polytope in $ \mathbb {R}$3 be partitioned into tetrahedra such that the dual graph has a Hamiltonian path?
Origin
[AHMS96].
Status/Conjectures
Open.
Partial and Related Results
Every convex polygon has such a Hamiltonian triangulation, but not every nonconvex polygon does [AHMS96]. The existence of a Hamiltonian path permits faster rendering on a graphics screen via pipelining.

Chin, Ding, and Wang [CDW05] have shown that examples exist for which the pulling tetrahedralization of a convex polytope is not Hamiltonian. (A pulling tetrahedralization is obtained by joining one vertex (the apex) to all other vertices of the polytope.) It is open if the shelling tetrahedralization may be always Hamiltonian.

Escalona et al. [EFMU07] prove the conjecture up to n = 20: every points set of n≤20 points admits a Hamiltonian Tetrahedralization. They also detail an algorithm that finds a Hamiltonian Tetrahedralization for n points by adding O(n) Steiner points. The algorithm runs in O(n3/2) time.

Appearances
[MO01]
Categories
triangulations; polyhedra
Entry Revision History
J. O'Rourke, 2 Aug. 2001; 13 Dec. 2001; J. Mitchell, 27 Oct. 2005; J. O'Rourke, 30 Sep. 2007.

Bibliography

AHMS96
Esther M. Arkin, Martin Held, Joseph S. B. Mitchell, and Steven S. Skiena.
Hamiltonian triangulations for fast rendering.
Visual Comput., 12(9):429-444, 1996.

CDW05
Francis Chin, Qing-Huai Ding, and Cao An Wang.
On Hamiltonian tetrahedralizations of convex polyhedra.
In Xiang-Sun Zhang, De-Gang Liu, and Ling-Yun Wu, editors, The Fifth International Symposium (ISORA 05), volume 5 of Operations Research and its Applications, Lecture Notes in Operations Research, pages 206-216. World Publishing Corporation, August 2005.

EFMU07
Francisco Escalona, Ruy Fabila-Monroy, and Jorge Urrutia.
Hamiltonian tetrahedralizations with steiner points.
In Abstracts 23rd European Worshop on Computational Geometry, pages 50-53, 2007.

MO01
J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573-582, 2001.
Also in SIGACT News 32(3):63-72 (2001), Issue 120.


next up previous
Next: Problem 30: Thrackles Up: The Open Problems Project Previous: Problem 28: Flip Graph
The Open Problems Project - December 04, 2015