TY - GEN

T1 - Linear time algorithms for visibility and shortest path problems inside simple polygons

AU - Guibas, Leo

AU - Hershberger, John

AU - Leven, Daniel

AU - Sharir, Micha

AU - Tarjan, Robert E.

N1 - Funding Information:
Work on this paper by the fourth author has been supportedb y Office of Naval Research Grant N00014-82-K-0381N, ational Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a Grant from the U.S-Israeli Binational ScienceF oundation.
Publisher Copyright:
© 1986 ACM.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 1986/8/1

Y1 - 1986/8/1

N2 - 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, as in [Ch]. (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.

AB - 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, as in [Ch]. (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.

UR - http://www.scopus.com/inward/record.url?scp=84990664534&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84990664534&partnerID=8YFLogxK

U2 - 10.1145/10515.10516

DO - 10.1145/10515.10516

M3 - Conference contribution

AN - SCOPUS:84990664534

T3 - Proceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986

SP - 1

EP - 13

BT - Proceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986

PB - Association for Computing Machinery, Inc

T2 - 2nd Annual Symposium on Computational Geometry, SCG 1986

Y2 - 2 June 1986 through 4 June 1986

ER -