Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414352 | Computational Geometry | 2006 | 11 Pages |
Abstract
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 , and the randomized algorithm runs in expected time O(kout+kinlogn+n(logn)1+ε). Here kin is the number of edges in all the paths of Π, and kout is the number of edges in the output paths.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics