Abstract
Consider an environment filled with polyhedral obstacles. The answer to a ray-shooting query is the first obstacle encountered by the ray. A simple way to answer ray-shooting queries is to triangulate space in a manner compatible with the obstacles, and then walk through the triangulation along the ray until the first obstacle is encountered. We show that the average walk length can be reduced by choosing a triangulation with weight (i.e., length in two dimensions or area in three dimensions) as small as possible. In two dimensions, we observe that the length of the minimum-length triangulation can be estimated by the total length of the obstacles plus the total length of a minimum spanning tree of the obstacles, up to a logarithmic factor; this gives an a priori estimate of the average-case walk length. Our main result is in three dimensions. We give a polynomial-time algorithm that computes a triangulation compatible with a set of polyhedral obstacles; the area of the triangulation is within a multiplicative constant of the smallest possible.
| Original language | English (US) |
|---|---|
| Pages | 203-211 |
| Number of pages | 9 |
| DOIs | |
| State | Published - 1997 |
| Event | Proceedings of the 1997 13th Annual Symposium on Computational Geometry - Nice, Fr Duration: Jun 4 1997 → Jun 6 1997 |
Other
| Other | Proceedings of the 1997 13th Annual Symposium on Computational Geometry |
|---|---|
| City | Nice, Fr |
| Period | 6/4/97 → 6/6/97 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics