Approximate minimum weight Steiner triangulation in three dimensions
Siu-Wing Cheng, Tamal K. Dey · 1999
Difficulty of minimum weight triangulation of a point set in R2 is well known. In this paper we study the minimum weight triangulation problem for polyhedra and general obstacle set in three dimensions. The weight of a triangulation in three dimensions is assumed to be the total surface area of all triangles involved. It is shown that a polyhedron P of size n can be triangulated with O(n2 log n) tetrahedra in time O(n2 log3 n) approximating the minimum weight triangulation of P within a constant factor. No such prior result is known. The same bounds also hold for a 3D point set triangulation allowing Steiner points. We consider another setting called general obstacle set, where the convex hull of a set of n triangles is triangulated conforming to the input triangles. In this case we show that our method produces a triangulation of size O(n3 log n) in time O(n3 log3 n) approximating the weight of the minimum weight triangulation within a constant factor. This is a considerable improvement over the O(n6) bound known for this case. It is shown in that minimum weight triangulation is good for average case ray shooting in three dimensions. This further substantiates the significance of our result.