Hamiltonian Tetrahedralizations with Steiner Points

Abstract

Let $S$ be a set of $n$ points in 3-dimensional space. A tetrahedralization $\mathcal{T}$ of $S$ is a set of interior disjoint tetrahedra with vertices on $S$, not containing points of $S$ in their interior, and such that their union is the convex hull of $S$. Given $\mathcal{T}$, $D_{\mathcal{T}}$ is defined as the graph having as vertex set the tetrahedra of $\mathcal{T}$, two of which are adjacent if they share a face. We say that $\mathcal{T}$ is Hamiltonian if $D_{\mathcal{T}}$ has a Hamiltonian path. Let $m$ be the number of convex hull vertices of $S$. We prove that by adding at most $\lfloor \frac{m-2}{2}\rfloor$ Steiner points to interior of the convex hull of $S$, we can obtain a point set that admits a Hamiltonian tetrahedralization. An $O(m^{3/2})+O(n\log n)$ time algorithm to obtain these points is given. We also show that all point sets with at most 20 convex hull points admit a Hamiltonian tetrahedralization without the addition of any Steiner points. Finally we exhibit a set of 84 points that does not admit a Hamiltonian tetrahedralization in which all tetrahedra share a vertex.

A conference version of this paper appeared in EuroCG' 07