LINEAR-TIME ALGORITHMS FOR VISIBILITY AND SHORTEST PATH PROBLEMS INSIDE TRIANGULATED SIMPLE POLYGONS.

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

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 journal › Article › peer-review

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 language	English (US)
Pages (from-to)	209-233
Number of pages	25
Journal	Algorithmica (New York)
Volume	2
Issue number	2
State	Published - 1987
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
Computer Science Applications
Applied Mathematics

Cite this

@article{315b6dad2b7546a39b685d6e46c4b646,

title = "LINEAR-TIME ALGORITHMS FOR VISIBILITY AND SHORTEST PATH PROBLEMS INSIDE TRIANGULATED SIMPLE POLYGONS.",

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

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

year = "1987",

language = "English (US)",

volume = "2",

pages = "209--233",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - LINEAR-TIME ALGORITHMS FOR VISIBILITY AND SHORTEST PATH PROBLEMS INSIDE TRIANGULATED SIMPLE POLYGONS.

AU - Guibas, Leonidas

AU - Hershberger, John

AU - Leven, Daniel

AU - Sharir, Micha

AU - Tarjan, Robert E.

PY - 1987

Y1 - 1987

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023247608&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023247608&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0023247608

SN - 0178-4617

VL - 2

SP - 209

EP - 233

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 2

ER -

LINEAR-TIME ALGORITHMS FOR VISIBILITY AND SHORTEST PATH PROBLEMS INSIDE TRIANGULATED SIMPLE POLYGONS.

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this