A New Algorithm for Euclidean Shortest Paths in the Plane
A New Algorithm for Euclidean Shortest Paths in the Plane
复制标题
平面上欧几里得最短路径的新算法
DOI：
10.1145/3580475
复制
发表时间：
2023
影响因子：
2.5
通讯作者：
Wang, Haitao
中科院分区：
文献类型：
--
作者：
Wang, Haitao
给定平面中一组成对不相交的多边形障碍物，寻找两点之间的避障欧几里德最短路径是计算几何中的经典问题，并且已被广泛研究。此前，Hershberger和Suri（inSIAM Journal onComputing，1999）给出了O(nlogn)时间和O(nlogn)空间的算法，其中n是所有障碍物的顶点总数。最近，Wang（在 SODA’21 中）通过修改 Hershberger 和 Suri 的算法，将空间减少到 O(n)，而算法的运行时间仍然是 O(nlogn)。在本文中，我们提出了一种新的 O(n+hlogh) 时间和 O(n) 空间算法，前提是给出自由空间的三角剖分，其中障碍物的数量。当其较小时，该算法比以前的工作要好。我们的算法为源点构建最短路径图，以便给定任何查询点，可以在 O(logn) 时间内计算出 stot 的最短路径长度，并且可以在与路径边数成线性关系的附加时间内生成最短 t 路径。
Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri (inSIAM Journal on Computing, 1999) gave an algorithm ofO(nlogn) time andO(nlogn) space, wherenis the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri’s algorithm, Wang (in SODA’21) reduced the space toO(n)while the runtime of the algorithm is stillO(nlogn). In this article, we present a new algorithm ofO(n+hlogh) time andO(n)space, provided that a triangulation of the free space is given, wherehis the number of obstacles. The algorithm is better than the previous work whenhis relatively small. Our algorithm builds a shortest path map for a source pointsso that given any query pointt, the shortest path length fromstotcan be computed inO(logn) time and a shortests-tpath can be produced in additional time linear in the number of edges of the path.