Approximating minimum-weight triangulations in three dimensions

Let S be a set of noncrossing triangular obstacles in R-3 With convex hull H. A triangulation I of H is compatible with S if every triangle of S is th e union of a subset of the faces of I. The weight of I is the sum of the ar eas of the triangles of I. We give a polynomial-time algorithm that compute s a triangulation compatible with S whose weight is at most a constant time s the weight of any compatible triangulation. One motivation for studying minimum-weight triangulations is a connection w ith 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 trian gulation along the ray, stopping at the first obstacle. Under a reasonably natural distribution of query rays, the average cost of a ray-shooting quer y is proportional to triangulation weight. A similar connection exists for line-stabbing queries ("Report all obstacles hit by a query line").