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

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

Research output: Contribution to journalArticlepeer-review

285 Scopus citations

Abstract

Given a triangulation of a simple polygon P, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility within P. These problems include calculation of the collection of all shortest paths inside P from a given source vertex S to all the other vertices of P, calculation of the subpolygon of P consisting of points that are visible from a given segment within P, preprocessing P for fast "ray shooting" queries, and several related problems.

Original languageEnglish (US)
Pages (from-to)209-233
Number of pages25
JournalAlgorithmica
Volume2
Issue number1
DOIs
StatePublished - Mar 1 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

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

Cite this