Research Information System
SIAM Journal on Computing, vol.51, no.4, pp.1296-1340, 2022 (SCI-Expanded)
© 2022 Society for Industrial and Applied Mathematics.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(n log n) 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(log n) 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(n log n + n log 1\e ). In fact, the algorithm computes an approximate shortest path map, a data structure with O(n log n) 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(log n) time. By applying an idea due to Wang [Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2021, pp. 810-821], the algorithm's working storage and the size of the approximate shortest path map can be reduced to O(n).