| Computing Homotopic Shortest Paths Efficiently (2008) | |||||||||||||||
Abstract | |||||||||||||||
| 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(log n)1(1+ε)), where k is the input plus output sizes of the paths. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||