Abstract
Given a triangulation of a simple polygon P, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility within P. These problems include calculation of the collection of all shortest paths inside P from a given source vertex s to all the other vertices of P, calculation of the subpolygon of P consisting of points that are visible from a given segment within P, preprocessing P for fast 'ray shooting' queries, and several related problems.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 209-233 |
| Number of pages | 25 |
| Journal | Algorithmica (New York) |
| Volume | 2 |
| Issue number | 2 |
| State | Published - 1987 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Computer Science
- Computer Science Applications
- Applied Mathematics