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

Leo Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

58 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986
PublisherAssociation for Computing Machinery, Inc
Pages1-13
Number of pages13
ISBN (Electronic)0897911946, 9780897911948
DOIs
StatePublished - Aug 1 1986
Event2nd Annual Symposium on Computational Geometry, SCG 1986 - Yorktown Heights, United States
Duration: Jun 2 1986Jun 4 1986

Publication series

NameProceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986

Other

Other2nd Annual Symposium on Computational Geometry, SCG 1986
CountryUnited States
CityYorktown Heights
Period6/2/866/4/86

All Science Journal Classification (ASJC) codes

  • Geometry and Topology
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Linear time algorithms for visibility and shortest path problems inside simple polygons'. Together they form a unique fingerprint.

Cite this