@inproceedings{1c40725f40c448b0a9cd6e09666e4041,

title = "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, 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.",

author = "Leo Guibas and John Hershberger and Daniel Leven and Micha Sharir and Tarjan, {Robert E.}",

year = "1986",

month = aug,

day = "1",

doi = "10.1145/10515.10516",

language = "English (US)",

series = "Proceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986",

publisher = "Association for Computing Machinery, Inc",

pages = "1--13",

booktitle = "Proceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986",

note = "2nd Annual Symposium on Computational Geometry, SCG 1986 ; Conference date: 02-06-1986 Through 04-06-1986",

}