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