An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane

S. Kapoor; S. N. Maheshwari; J. S.B. Mitchell

doi:10.1007/PL00009323

An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane

S. Kapoor
, S. N. Maheshwari
, J. S.B. Mitchell

Applied Mathematics and Statistics

Indian Institute of Technology Delhi

Research output: Contribution to journal › Article › peer-review

82 Scopus citations

Abstract

We give an algorithm to compute a (Euclidean) shortest path in a polygon with h holes and a total of n vertices. The algorithm uses O (n) space and requires O (n + h² log n) time.

Original language	English
Pages (from-to)	377-383
Number of pages	7
Journal	Discrete and Computational Geometry
Volume	18
Issue number	4
DOIs	https://doi.org/10.1007/PL00009323
State	Published - Dec 1997

Access to Document

10.1007/PL00009323

Cite this

@article{d6cd701104ac4e3e899f84579d788fd4,

title = "An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane",

abstract = "We give an algorithm to compute a (Euclidean) shortest path in a polygon with h holes and a total of n vertices. The algorithm uses O (n) space and requires O (n + h2 log n) time.",

author = "S. Kapoor and Maheshwari, \{S. N.\} and Mitchell, \{J. S.B.\}",

year = "1997",

month = dec,

doi = "10.1007/PL00009323",

language = "English",

volume = "18",

pages = "377--383",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

number = "4",

}

TY - JOUR

T1 - An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane

AU - Kapoor, S.

AU - Maheshwari, S. N.

AU - Mitchell, J. S.B.

PY - 1997/12

Y1 - 1997/12

N2 - We give an algorithm to compute a (Euclidean) shortest path in a polygon with h holes and a total of n vertices. The algorithm uses O (n) space and requires O (n + h2 log n) time.

AB - We give an algorithm to compute a (Euclidean) shortest path in a polygon with h holes and a total of n vertices. The algorithm uses O (n) space and requires O (n + h2 log n) time.

UR - https://www.scopus.com/pages/publications/0031502943

U2 - 10.1007/PL00009323

DO - 10.1007/PL00009323

M3 - Article

AN - SCOPUS:0031502943

SN - 0179-5376

VL - 18

SP - 377

EP - 383

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -

An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane

Abstract

Access to Document

Other files and links

Fingerprint

Cite this