Computing homotopic shortest paths in the plane
Sergei N. Bespamyatnikh · Symposium on Discrete Algorithms · 2003
We address the problem of computing homotopic shortest paths in presence of obstacles in the plane. The problems on homotopy of the paths received attention very recently [3, 8]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [8]. The algorithm for non-simple paths achieves O(log2n) time per output vertex which is an improvement by a factor of O(n/log2n) of the previous algorithm [13] where n is the number of obstacles.