Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons.
01 January 1987
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 with P, preprocessing P for fast "ray shooting" queries, and several related problems.