Computing Homotopic Shortest Paths in the Plane

Abstract: We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane.

Shortest Homotopic Path (SHP) Problem. Given np disjoint paths and nb point barriers, find shortest homotopic paths. We assume that the endpoints of the paths are barriers as well. Let n=2np+nb be the total number of barriers.
The problems on homotopy of the paths received attention very recently [1,2]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths runs in O(nlog1+en+ kinlog n+kout) time improving the previous algorithm [2]. The algorithm for non-simple paths achieves O(log2 n) time per output vertex improving the previous algorithm [3] by a factor of O(n/log2 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
}