On Hamiltonian tetrahedralizations of convex polyhedra

Let T-p denote any tetrahedralization of a convex polyhedron P and let G(T) be the dual graph of T-p such that each node of G(T) corresponds to a tetrahedron of T-p and two nodes are connected by an edge in G(T) if and only if the two corresponding tetrahedra share a common facet in T-p. T-p is called a Hamiltonian tetrahedralization if G(T) contains a Hamiltonian path (HP). A well-known open problem in computational geometry is: can every polytope in 3D be partitioned into tetrahedra such that the dual graph has an HP? In this note, we shall show that there exists a 92-vertex polyhedron in which the pulling method does not yield a Hamiltonian tetrahedralization, here the pulling method is the simplest method to ensure a linear-size decomposition and is one of the most commonly used tetrahedralization methods for convex polyhedra. Furthermore, we can construct a convex polyhedron with n vertices such that the longest path in the dual graph in question can be as short as 0(l). This fact suggests that it may not be possible to find a good approximation of a HP for convex polyhedra using the pulling method.