## Computing Homotopic Shortest Paths in the Plane
O(nlog^{1+e}n+
klog _{in}n+k) time improving the previous
algorithm [2]. The algorithm for non-simple paths achieves
_{out}O(log^{2} n) time per output vertex
improving the previous algorithm [3] by a factor of
O(n/log^{2} n).
[1] S. Cabello, Y. Liu, A. Mantler, and J. Snoeyink. Testing homotopy for paths in the plane. In Proc. 18th Annu. ACM Symp. Comput. Geom., pp. 160--169, 2002. [2] A. Efrat, S. Kobourov, and A. Lubiw. Computing homotopic shortest paths efficiently. In Proc. 10th Annu. European Sympos. Algorithms, 2002. [3] J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. Comput. Geom. Theory Appl., 4:63-98, 1994. @article{b-chspp-03 , author = "S. Bespamyatnikh" , title = "Computing Homotopic Shortest Paths in the Plane" , journal = "J. Algorithms" , volume = 49 , number = 2 , pages = "284--303" , year = 2003 , url = "http://authors.elsevier.com/sd/article/S0196677403000907" } @inproceedings{b-chspp-03 , author = "S. Bespamyatnikh" , title = "Computing Homotopic Shortest Paths in the Plane" , booktitle = "Proc. 14th ACM-SIAM Sympos. Discrete Algorithms" , pages = "609--617" , year = 2003 } |