## Abstract

Let S be a set of noncrossing triangular obstacles in ℝ^{3} 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").

Original language | English (US) |
---|---|

Pages (from-to) | 527-549 |

Number of pages | 23 |

Journal | Discrete and Computational Geometry |

Volume | 21 |

Issue number | 4 |

DOIs | |

State | Published - Jun 1999 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics