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 -