A near-optimal algorithm for shortest paths among curved obstacles in the plane

We propose an algorithm for the problem of computing shortest paths among curved obstacles in the plane. If the obstacles have O(n) description complexity, then the algorithm runs in O(nlogn) time plus a term dependent on the properties of the boundary arcs. Specifically, if the arcs allow a certain kind of bisector intersection to be computed in constant time, or even in O(logn) time, then the running time of the overall algorithm is O(n log n). If the arcs support only constant-time tangent, intersection, and length queries, as is customarily assumed, then the algorithm computes an approximate shortest path, with relative error ε, in time O(nlogn + nlog 1/ε). In fact, the algorithm computes an approximate shortest path map, a data structure with O(n logn) size, that allows it to report the (approximate) length of a shortest path from a fixed source point to any query point in the plane in O(logn) time. Copyright 2013 ACM