Let
S be a set of noncrossing triangular
obstacles in
R
3
with convex hull
H . A triangulation
T of
H is
compatible with
S if every triangle of
S is the union of a subset of the faces of
T. The
weight of
T is the sum of the areas of the triangles of
T. 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'').
Received February 3, 1997, and in revised form August 21, 1998.