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 - http://www.scopus.com/inward/record.url?scp=84867977487&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867977487&partnerID=8YFLogxK
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 -