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 |
Volume | 2 |
Issue number | 1 |
DOIs | |
State | Published - Mar 1 1987 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Computer Science Applications
- Applied Mathematics