Published on *Computer Science Department at Princeton University* (https://www.cs.princeton.edu)

Report ID:

TR-039-86

Authors:

Guibas, Leonidas [1] / Hershberger, John [2] / Leven, Daniel [3] / Sharir, Micha [4] / Tarjan, Robert E. [5]

Date:

April 1986

Pages:

50

Download Formats:

[PDF [6]]

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.

**Links**

[1] https://www.cs.princeton.edu/research/techreps/author/417

[2] https://www.cs.princeton.edu/research/techreps/author/424

[3] https://www.cs.princeton.edu/research/techreps/author/111

[4] https://www.cs.princeton.edu/research/techreps/author/461

[5] https://www.cs.princeton.edu/research/techreps/author/384

[6] ftp://ftp.cs.princeton.edu/techreports/1986/039.pdf