Shortest Paths Among Obstacles in the Plane Revisited
Shortest Paths Among Obstacles in the Plane Revisited
复制标题
重新审视平面障碍物中的最短路径
DOI：
10.1137/1.9781611976465.51
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Wang, Haitao
中科院分区：
文献类型：
--
作者：
Wang, Haitao
给定平面中一组成对不相交的多边形障碍物，寻找两点之间的避障欧几里德最短路径是计算几何中的经典问题，并且已被广泛研究。之前的最佳算法是由 Hershberger 和 Suri 给出的 [FOCS 1993, SIAM J. Comput。 1999]并且算法运行在O(nlogn)时间和O(nlogn)空间中，其中n是所有障碍物的顶点总数。该算法是时间最优的，因为 Ω(nlogn) 是下界。二十多年来，空间是否可以减少到 O(n) 一直是一个悬而未决的问题。本文通过求解O(nlogn)时间和O(n)空间的问题来解决，在时间和空间上都是最优的；我们通过修改 Hershberger 和 Suri 的算法来实现这一点。与他们的原始算法一样，我们的新算法可以在 O(nlogn) 时间和 O(n) 空间中为源点构建最短路径图，这样给定任何查询点，可以在 O(logn) 时间内计算出从 stot 开始的最短路径的长度，并且可以在额外的时间内生成与路径边数成线性关系的最短路径。
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. The previous best algorithm was given by Hershberger and Suri [FOCS 1993, SIAM J. Comput. 1999] and the algorithm runs inO(nlogn) time andO(nlogn) space, wherenis the total number of vertices of all obstacles. The algorithm is time-optimal because Ω(nlogn) is a lower bound. It has been an open problem for over two decades whether the space can be reduced toO(n). In this paper, we settle it by solving the problem inO(nlogn) time andO(n) space, which is optimal in both time and space; we achieve this by modifying the algorithm of Hershberger and Suri. Like their original algorithm, our new algorithm can build a shortest path map for a source pointsinO(nlogn) time andO(n) space, such that given any query pointt, the length of a shortest path fromstotcan be computed inO(logn) time and a shortest path can be produced in additional time linear in the number of edges of the path.
登录
查看更多内容
简单多边形点测地线Voronoi图的近乎最优算法
影响因子：
1.1
作者：
Chih
通讯作者：
Chih
DOI：
--
发表时间：
2013
期刊：
International Symposium on Computational Geometry
影响因子：
--
作者：
J. Hershberger;S. Suri;Hakan Yildiz
通讯作者：
Hakan Yildiz
简单多边形中中等大小点集的 Voronoi 图
影响因子：
0.8
作者：
Eunjin Oh;Hee
通讯作者：
Hee
简单多边形中最短路径查询的新数据结构
DOI：
10.1016/0020-0190(91)90064-o
发表时间：
1991
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
J. Hershberger
通讯作者：
J. Hershberger
影响因子：
1.2
作者：
Joseph S. B. Mitchell
通讯作者：
Joseph S. B. Mitchell