L1 shortest paths among polygonal obstacles in the plane
L1 shortest paths among polygonal obstacles in the plane
复制标题
DOI：
10.1007/bf01758836
复制
发表时间：
1992-12
期刊：
影响因子：
1.1
通讯作者：
Joseph S. B. Mitchell
中科院分区：
文献类型：
--
作者：
Joseph S. B. Mitchell
提出了一种计算平面内多边形障碍物间L1最短路径的算法。我们的算法使用“连续Dijkstra”技术传播一个“波前”，在时间(Elogn)和空间O(E)上运行，其中是障碍物的顶点数，E是“事件”的数目。利用某些稀疏二进制阵密度的界，我们证明了它=O(Nlogn)，这意味着我们的算法是接近最优的。我们猜想Thate=O(N)，这意味着我们的算法是最优的。该算法推广到固定方向度量的情况，给出了求解障碍间欧几里得最短路径的ANO(nɛ−1/2log2n)时间和nɛ−1/2空间近似算法。该算法进一步推广到许多源的情况，允许我们计算位于多边形障碍物集合中的源点的L1Voronoi图。
We present an algorithm for computingL1shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in timeO(Elogn) and spaceO(E), wherenis the number of vertices of the obstacles andEis the number of “events.” By using bounds on the density of certain sparse binary matrices, we show thatE=O(nlogn), implying that our algorithm is nearly optimal. We conjecture thatE=O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space.Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(nɛ−1/2log2n) time andO(nɛ−1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL1Voronoi diagram for source points that lie among a collection of polygonal obstacles.