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, Brezilya, 17 - 20 Haziran 2013, ss.359-368 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1145/2462356.2462374
  • Basıldığı Şehir: Rio de Janeiro
  • Basıldığı Ülke: Brezilya
  • Sayfa Sayıları: ss.359-368
  • Anahtar Kelimeler: Continuous dijkstra, Curved obstacles, Polygo-nization, Shortest paths
  • Orta Doğu Teknik Üniversitesi Adresli: Hayır

Özet

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.