Next: Problem 30: Thrackles
Previous: Problem 28: Flip Graph Connectivity in 3D
Can every convex polytope in \R^3 be partitioned into tetrahedra such that the dual graph has a Hamiltonian path?
Open.
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.
triangulations; polyhedra
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. . 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.