Hamiltonian Tetrahedralizations
Can every convex polytope in be partitioned into tetrahedra such that the dual graph has a Hamiltonian path? Here the dual graph of a tetrahedral partition has one vertex for each tetrahedron, with two vertices adjacent exactly when their tetrahedra share a triangular face. A Hamiltonian path is a sequence of distinct vertices that visits every vertex of the graph, with consecutive vertices adjacent. Thus the question asks whether, for every three-dimensional convex polytope , there is a finite partition of into tetrahedra, with pairwise disjoint interiors, whose dual graph has such a path. Open Problems Project, Problem 29
Background
The problem is listed as Problem 29 in the computational-geometry problem collection and is attributed to work of Arkin, Held, Mitchell, and Skiena from 1996. Hamiltonian triangulations were studied in part because a path through adjacent simplices allows them to be sent to a graphics processor in a pipelined order; the same motivation applies to tetrahedralizations. In the planar comparison recorded with the problem, every convex polygon has a Hamiltonian triangulation, whereas some nonconvex polygons do not. Open Problems Project, Problem 29 Mitchell and O’Rourke, Computational Geometry Column 42 (2001)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.