Tetrahedralization of two nested convex polyhedra

In this paper, we present an algorithm to tetrahedralize the region between two nested convex polyhedra without introducing Steiner points. The resulting tetrahedralization consists of linear number of tetrahedra. Thus, we answer the open problem raised by Chazelle and Shouraboura [6]: whether or not one can tetrahedralize the region between two nested convex polyhedra into linear number of tetrahedra, avoiding Steiner points?. Our algorithm runs in O((n+m) 3 log(n+m)) time and produces 2(m + n - 3) tetrahedra, where n and m are the numbers of the vertices in the two given polyhedra, respectively.