Optimal Tetrahedralization of the 3d-Region between a Convex Polyhedron and a Convex Polygon.
Leonidas Palios · Canadian Conference on Computational Geometry · 1994
Abstract Given a convex polyhedron P and a convex polygon Q in R3 such that Q′s supporting plane does not intersect P, we are interested in tetrahedralizing the closure of the difference convex_hull(P ∪ Q) ⧹ P; since P is convex, this difference is a connected nonconvex subset of R3 which we call the region “between” P and Q. The problem is motivated by the work of Bern on tetrahedralizing the region between convex polyhedra (Bern, 1993). In this paper, we describe a novel approach that yields an optimal tetrahedralization, that is, O(n) tetrahedra and no Steiner points; the tetrahedralization is compatible with the boundary of the polyhedron P, and can be computed in optimal O(n) time. Our result also implies a simple and optimal algorithm for the side-by-side case (Bern, 1993) when Steiner points are allowed: the region “between” two non-intersecting convex polyhedra of total size n can be partitioned into O(n) tetrahedra using O(n) Steiner points; as above, the tetrahedralization is compatible with the boundaries of the two polyhedra, and can be computed in O(n) time. Note that if Steiner points are not allowed, instances of side-by-side convex polyhedra lead to tetrahedralizations quadratic in their sizes.