Hamiltonian Tetrahedralizations

Can every convex polytope in $\mathbb{R}^3$ be partitioned into tetrahedra such that the dual graph has a Hamiltonian path?

Download

Abstract

Determine whether every convex three-dimensional polytope has a tetrahedralization whose dual graph contains a Hamiltonian path.

Background and progress

Hamiltonian tetrahedralizations arise in geometric processing [Arkin et al., 1996]. The property has been verified for small instances, and constructions with Steiner points are known [Escalona et al., 2007]; the Steiner-free question remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p29.

Reference papers

Hamiltonian triangulations for fast renderingEsther M. Arkin, Mark de Berg, Joseph S. B. Mitchell, Steven S. SkienaThe Visual Computer · 1996
Hamiltonian tetrahedralizations with Steiner pointsFrancisco Escalona, Ruy Fabila-Monroy, Jorge UrrutiaJapan Conference on Discrete and Computational Geometry · 2007

Hamiltonian Tetrahedralizations

Coming soon

Organizer