Hamiltonian Tetrahedralizations

Given a convex polytope $P\subset\mathbb{R}^3$ , does there always exist a tetrahedralization of $P$ , using only vertices of $P$ , such that the dual adjacency graph of its tetrahedra 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