A near-optimal algorithm for shortest paths among curved obstacles in the plane
A near-optimal algorithm for shortest paths among curved obstacles in the plane
复制标题
平面内弯曲障碍物间最短路径的近优算法
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Hakan Yildiz
中科院分区：
文献类型：
--
作者：
J. Hershberger;S. Suri;Hakan Yildiz
针对平面上弯曲障碍物间最短路径的计算问题，提出了一种算法。如果障碍物的描述复杂度为O(n)，则算法运行的时间为O（n log n）加上一个取决于边界弧性质的项。具体来说，如果弧允许在常数时间内，甚至在O（log n）时间内计算出某一种平分线的交点，则整个算法的运行时间为O（n log n）。如果弧线只支持常时切线、交点和长度查询，如通常假设的那样，则算法计算出一个近似最短路径，相对误差为ε，时间为O（n log n + n log 1/ε）。实际上，该算法计算一个近似的最短路径映射，这是一个大小为O（n log n）的数据结构，允许它在O（log n）时间内报告从固定源点到平面上任何查询点的最短路径的（近似）长度。
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/ε). 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.