Approximating minimum-weight triangulations in three dimensions

Let S be a set of noncrossing triangular obstacles in ℝ³ with convex hull H. A triangulation Script T sign of H is compatible with S if every triangle of S is the union of a subset of the faces of Script T sign. The weight of Script T sign is the sum of the areas of the triangles of Script T sign. We give a polynomial-time algorithm that computes a triangulation compatible with S whose weight is at most a constant times the weight of any compatible triangulation. One motivation for studying minimum-weight triangulations is a connection with ray shooting. A particularly simple way to answer a ray-shooting query ("Report the first obstacle hit by a query ray") is to walk through a triangulation along the ray, stopping at the first obstacle. Under a reasonably natural distribution of query rays, the average cost of a ray-shooting query is proportional to triangulation weight. A similar connection exists for line-stabbing queries ("Report all obstacles hit by a query line").