Computing homotopic shortest paths efficiently

Alon Efrat; Stephen G. Kobourov; Anna Lubiw

doi:10.1007/3-540-45749-6_38

Computing homotopic shortest paths efficiently

Alon Efrat, Stephen G. Kobourov, Anna Lubiw

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

18 Scopus citations

Abstract

We give algorithms to find shortest paths homotopic to given disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k log n+n√n), and the randomized version in time O(k log n + n(logn)^1+ε), where k is the input plus output sizes of the paths.

Original language	English (US)
Title of host publication	Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
Editors	Rolf Möhring, Rajeev Raman
Publisher	Springer-Verlag
Pages	411-423
Number of pages	13
ISBN (Electronic)	3540441808, 9783540441809
DOIs	https://doi.org/10.1007/3-540-45749-6_38
State	Published - 2002
Event	10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy Duration: Sep 17 2002 → Sep 21 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2461
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	10th Annual European Symposium on Algorithms, ESA 2002
Country/Territory	Italy
City	Rome
Period	9/17/02 → 9/21/02

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-45749-6_38

Cite this

Efrat, A., Kobourov, S. G., & Lubiw, A. (2002). Computing homotopic shortest paths efficiently. In R. Möhring, & R. Raman (Eds.), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings (pp. 411-423). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2461). Springer-Verlag. https://doi.org/10.1007/3-540-45749-6_38

Computing homotopic shortest paths efficiently. / Efrat, Alon ; Kobourov, Stephen G.; Lubiw, Anna.

Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. ed. / Rolf Möhring; Rajeev Raman. Springer-Verlag, 2002. p. 411-423 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2461).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Efrat, A , Kobourov, SG & Lubiw, A 2002, Computing homotopic shortest paths efficiently. in R Möhring & R Raman (eds), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2461, Springer-Verlag, pp. 411-423, 10th Annual European Symposium on Algorithms, ESA 2002, Rome, Italy, 9/17/02. https://doi.org/10.1007/3-540-45749-6_38

Efrat A , Kobourov SG, Lubiw A. Computing homotopic shortest paths efficiently. In Möhring R, Raman R, editors, Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. Springer-Verlag. 2002. p. 411-423. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-45749-6_38

Efrat, Alon ; Kobourov, Stephen G. ; Lubiw, Anna. / Computing homotopic shortest paths efficiently. Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings. editor / Rolf Möhring ; Rajeev Raman. Springer-Verlag, 2002. pp. 411-423 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c70ce1c4c6224c07883bbd09056262af,

title = "Computing homotopic shortest paths efficiently",

abstract = "We give algorithms to find shortest paths homotopic to given disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k log n+n√n), and the randomized version in time O(k log n + n(logn)1+ε), where k is the input plus output sizes of the paths.",

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: alon@cs.arizona.edu (A. Efrat), kobourov@cs.arizona.edu (S.G. Kobourov), alubiw@uwaterloo.ca (A. Lubiw). 1 Partially supported by the NSF under grant ACR-0222920. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 10th Annual European Symposium on Algorithms, ESA 2002 ; Conference date: 17-09-2002 Through 21-09-2002",

year = "2002",

doi = "10.1007/3-540-45749-6_38",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "411--423",

editor = "Rolf M{\"o}hring and Rajeev Raman",

booktitle = "Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings",

}

TY - GEN

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: alon@cs.arizona.edu (A. Efrat), kobourov@cs.arizona.edu (S.G. Kobourov), alubiw@uwaterloo.ca (A. Lubiw). 1 Partially supported by the NSF under grant ACR-0222920. Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - We give algorithms to find shortest paths homotopic to given disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k log n+n√n), and the randomized version in time O(k log n + n(logn)1+ε), where k is the input plus output sizes of the paths.

AB - We give algorithms to find shortest paths homotopic to given disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k log n+n√n), and the randomized version in time O(k log n + n(logn)1+ε), where k is the input plus output sizes of the paths.

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

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

U2 - 10.1007/3-540-45749-6_38

DO - 10.1007/3-540-45749-6_38

M3 - Conference contribution

AN - SCOPUS:84938062776

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 411

EP - 423

BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings

A2 - Möhring, Rolf

A2 - Raman, Rajeev

PB - Springer-Verlag

T2 - 10th Annual European Symposium on Algorithms, ESA 2002

Y2 - 17 September 2002 through 21 September 2002

ER -

Computing homotopic shortest paths efficiently

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this