Linear Time Algorithms for Visibility and Shortest Path Problems Inside Simple Polygons

Abstract:

We present linear time algorithms for solving the following problems involving a simple planar polygon P: (i) Computing the collection of all shortest paths inside P from a given source vertex s to all the other vertices of P; (ii) computing the subpolygon of P consisting of points that are visible from a
segment within P; (iii) preprocessing P so that for any query ray r emerging from some fixed edge e of P, we can find in logarithmic time the first intersection of r with the boundary of P; (iv) preprocessing P so that for any query point x in P, we can find in logarithmic time the portion of the edge e that is visible from x; (v) preprocessing P so that for any query point x inside P and direction u, we can find in logarithmic time the first point on the boundary of P hit by the ray at direction u from x; (vi) calculating a hierarchical decomposition of P into smaller polygons by recursive polygon cutting; and (vii) calculating the (clockwise and counterclockwise) "convex ropes" (in the terminology of [PS]) from a fixed vertex s of P lying on its convex hull, to all other vertices of P. All these algorithms are based on a recent linear time algorithm of Tarjan and Van Wyk for triangulating a simple polygon, but use additional techniques to make all subsequent phases of these algorithms also linear.