Computing homotopic shortest paths efficiently

Alon Efrat; Stephen G. Kobourov; Anna Lubiw

doi:10.1016/j.comgeo.2006.03.003

Computing homotopic shortest paths efficiently

Computer Science

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

37 Scopus citations

Abstract

We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k _out+k _inlogn+n√n), and the randomized algorithm runs in expected time O(k _out+k ⁱⁿlogn+n(logn) ^1+ε). Here k ⁱⁿ is the number of edges in all the paths of Π, and k ^out is the number of edges in the output paths.

Original language	English (US)
Pages (from-to)	162-172
Number of pages	11
Journal	Computational Geometry: Theory and Applications
Volume	35
Issue number	3
DOIs	https://doi.org/10.1016/j.comgeo.2006.03.003
State	Published - Oct 2006

Keywords

Homotopic shortest paths
Shortest path in a polygon

ASJC Scopus subject areas

Computer Science Applications
Geometry and Topology
Control and Optimization
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/j.comgeo.2006.03.003

Cite this

@article{db2a4e7f133c41cc8a62e428f8275f69,

title = "Computing homotopic shortest paths efficiently",

abstract = "We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k out+k inlogn+n√n), and the randomized algorithm runs in expected time O(k out+k inlogn+n(logn) 1+ε). Here k in is the number of edges in all the paths of Π, and k out is the number of edges in the output paths.",

keywords = "Homotopic shortest paths, Shortest path in a polygon",

author = "Alon Efrat and Kobourov, \{Stephen G.\} and Anna Lubiw",

note = "Funding Information: A preliminary version of this paper appeared in the 10th European Symposium on Algorithms (ESA), 2002, pp. 411–423. Corresponding author. E-mail addresses: [email protected] (A. Efrat), [email protected] (S.G. Kobourov), [email protected] (A. Lubiw). 1 Partially supported by the NSF under grant ACR-0222920.",

year = "2006",

month = oct,

doi = "10.1016/j.comgeo.2006.03.003",

language = "English (US)",

volume = "35",

pages = "162--172",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Computing homotopic shortest paths efficiently

AU - Efrat, Alon

AU - Kobourov, Stephen G.

AU - Lubiw, Anna

N1 - Funding Information: A preliminary version of this paper appeared in the 10th European Symposium on Algorithms (ESA), 2002, pp. 411–423. Corresponding author. E-mail addresses: [email protected] (A. Efrat), [email protected] (S.G. Kobourov), [email protected] (A. Lubiw). 1 Partially supported by the NSF under grant ACR-0222920.

PY - 2006/10

Y1 - 2006/10

N2 - We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k out+k inlogn+n√n), and the randomized algorithm runs in expected time O(k out+k inlogn+n(logn) 1+ε). Here k in is the number of edges in all the paths of Π, and k out is the number of edges in the output paths.

AB - We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k out+k inlogn+n√n), and the randomized algorithm runs in expected time O(k out+k inlogn+n(logn) 1+ε). Here k in is the number of edges in all the paths of Π, and k out is the number of edges in the output paths.

KW - Homotopic shortest paths

KW - Shortest path in a polygon

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

UR - https://www.scopus.com/pages/publications/84867977487#tab=citedBy

U2 - 10.1016/j.comgeo.2006.03.003

DO - 10.1016/j.comgeo.2006.03.003

M3 - Article

AN - SCOPUS:84867977487

SN - 0925-7721

VL - 35

SP - 162

EP - 172

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 3

ER -

Computing homotopic shortest paths efficiently

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this