← All problems

Hamiltonian Tetrahedralizations

30 years old · traced to

Can every convex polytope in R3\mathbb{R}^3 be partitioned into tetrahedra such that the dual graph has a Hamiltonian path? Here the dual graph of a tetrahedral partition T\mathcal{T} 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 P⊂R3P\subset\mathbb{R}^3, there is a finite partition T\mathcal{T} of PP 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)

References

Progress summary

Never refreshed

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.