Approximating Minimum-Weight Triangulations in Three Dimensions |
| |
Authors: | B Aronov S Fortune |
| |
Institution: | (1) Computer and Information Science, Polytechnic University, Brooklyn, NY 11201, USA aronov@ziggy.poly.edu, US;(2) Bell Laboratories, Murray Hill, NJ 07974, USA sjf@research.bell-labs.com, US |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|