A new algorithm for shortest paths among obstacles in the plane
A new algorithm for shortest paths among obstacles in the plane
复制标题
平面障碍物间最短路径的新算法
DOI：
--
复制
发表时间：
1991
影响因子：
1.2
通讯作者：
Joseph S. B. Mitchell
中科院分区：
文献类型：
--
作者：
Joseph S. B. Mitchell
提出了一种计算平面上存在多边形障碍物的欧几里德最短路的新算法。特别地，对于给定的起始点，我们建立了一个平面剖分(最短路径图)，它支持高效地查询从任意终点到任意终点的最短路径。算法的最坏情况时间复杂度为ISO(Kn Log2n)，其中n是描述多边形障碍物的顶点数，k是我们称之为障碍空间的照明深度的参数。我们的算法使用O(N)空间，避免了依赖可见图的方法可能的二次空间复杂性。数量k通常明显小于n，特别是在可见性图具有平方大小的某些情况下。具体地说，k以上的界限是接触任何最短路径的不同障碍物的数量。
We introduce a new algorithm for computing Euclidean shortest paths in the plane in the presence of polygonal obstacles. In particular, for a given start points, we build a planar subdivision (ashortest path map) that supports efficient queries for shortest paths froms to any destination pointt. The worst-case time complexity of our algorithm isO(kn log2n), wheren is the number of vertices describing the polygonal obstacles, andk is a parameter we call the “illumination depth” of the obstacle space. Our algorithm usesO(n) space, avoiding the possibly quadratic space complexity of methods that rely on visibility graphs. The quantityk is frequently significantly smaller thann, especially in some of the cases in which the visibility graph has quadratic size. In particular,k is bounded above by the number of different obstacles that touch any shortest path froms.