A new algorithm for Euclidean shortest paths in the plane
A new algorithm for Euclidean shortest paths in the plane
复制标题
平面内欧氏最短路径的新算法
DOI：
10.1145/3406325.3451037
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Wang, Haitao
中科院分区：
文献类型：
--
作者：
Wang, Haitao
给定平面上一组两两不相交的多边形障碍物，寻找两点间的欧几里得避障最短路径是计算几何中的一个经典问题，得到了广泛的研究。以前，Hershberger和Suri(在SIAM计算杂志上，1999)给出了一个算法，它是指所有障碍物的顶点总数。最近，通过修改Hershberger和Suri的算法，Wang(在Soda‘21中)也减少了空间(N)，而算法的运行时间是Stillo(Nlogn)。在本文中，我们提出了一个新的算法，在给定自由空间的三角剖分的情况下，给出了一个新的(n+hlogh)时间Ando(N)空间算法。该算法优于前人在HIS相对较小的时候所做的工作。我们的算法建立了一个源点的最短路径图，使得在给定任何一个查询点的情况下，距离该点的最短路径长度可以在o(Logn)时间内计算出来，并且可以在额外的时间内产生与路径边数成线性关系的最短路径。
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.
登录
查看更多内容
C G ] 2 0 Sep 20 18 L 1 简单多边形中的最短路径查询
DOI：
--
发表时间：
2018
期刊：
影响因子：
--
作者：
S. Bae;Haitao Wang
通讯作者：
Haitao Wang
影响因子：
1.1
作者：
Joseph S. B. Mitchell
通讯作者：
Joseph S. B. Mitchell
DOI：
--
发表时间：
2013
期刊：
International Symposium on Computational Geometry
影响因子：
--
作者：
J. Hershberger;S. Suri;Hakan Yildiz
通讯作者：
Hakan Yildiz
DOI：
--
发表时间：
2000
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
S. Kapoor;S. Maheshwari
通讯作者：
S. Maheshwari
重新审视平面障碍物中的最短路径
DOI：
10.1137/1.9781611976465.51
发表时间：
2021
期刊：
Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021
影响因子：
--
作者：
Wang, Haitao
通讯作者：
Wang, Haitao