Problem 29: Hamiltonian Tetrahedralizations

Statement

Can every convex polytope in $\mathbb {R}$³ 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$\le$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(n^3/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.