A NEAR-OPTIMAL ALGORITHM FOR SHORTEST PATHS AMONG CURVED OBSTACLES IN THE PLANE

作     者：Hershberger, John Suri, Subhash Yildiz, Hakan 

作者机构：Siemens EDA WilsonvilleOR97070 United States Department of Computer Science UC Santa Barbara Santa BarbaraCA93106 United States Department of Computer Engineering Middle East Technical University Ankara Turkey 

出 版 物：《SIAM Journal on Computing》 (SIAM J Comput)

年 卷 期：2022年第51卷第4期

页      面：1296-1340页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

主　　题：Digital storage 

摘      要：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). © 2022 Society for Industrial and Applied Mathematics.