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


Creative Commons License

Hershberger J., Suri S., Yildiz H.

29th Annual Symposium on Computational Geometry, SoCG 2013, Rio de Janeiro, Brazil, 17 - 20 June 2013, pp.359-368 identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1145/2462356.2462374
  • City: Rio de Janeiro
  • Country: Brazil
  • Page Numbers: pp.359-368
  • Keywords: Continuous dijkstra, Curved obstacles, Polygo-nization, Shortest paths

Abstract

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.