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

286 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 (New York)
Volume2
Issue number2
StatePublished - 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • 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