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

Problem 29: Hamiltonian Tetrahedralizations

Can every convex polytope in $ \mathbb {R}$3 be partitioned into tetrahedra such that the dual graph has a Hamiltonian path?
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.

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.


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.

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.

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.

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