Shortest paths in the plane with polygonal obstacles
Shortest paths in the plane with polygonal obstacles
复制标题
DOI：
10.1145/185675.185795
复制
发表时间：
1994-09
期刊：
影响因子：
--
通讯作者：
J. Storer;J. Reif
中科院分区：
文献类型：
--
作者：
J. Storer;J. Reif
我们提出了一个实用的算法，在欧几里得平面（不一定是凸的）多边形障碍物的点之间的最小长度路径。在此之前的工作，最有名的算法，寻找最短路径之间的两点在平面上需要（n2 log n）的时间和O（n2）的空间，其中n表示障碍边缘的数量。假设障碍空间的三角剖分或Voronoi图的输入（如果不是，任何一个可以预先计算在O（n log n）时间），我们提出了一个O（kn）时间算法，其中k表示的“岛”（连接组件）在障碍空间的数量。该算法仅使用O（n）空间，并且给定源点s，产生O（n）大小的数据结构，使得s与平面（x）中的任何其他点x之间的距离（不一定是障碍顶点或障碍边缘上的点）可以在O（1）时间内计算。该算法还可以用于计算磁盘移动的最短路径（因此可以计算任意对象的最佳移动，以将其与最小可能的磁盘包围在一起）。
We present a practical algorithm for finding minimum-length paths between points in the Euclidean plane with (not necessarily convex) polygonal obstacles. Prior to this work, the best known algorithm for finding the shortest path between two points in the plane required &OHgr;(n2 log n) time and O(n2) space, where n denotes the number of obstacle edges. Assuming that a triangulation or a Voronoi diagram for the obstacle space is provided with the input (if is not, either one can be precomputed in O(n log n) time), we present an O(kn) time algorithm, where k denotes the number of “islands” (connected components) in the obstacle space. The algorithm uses only O(n) space and, given a source point s, produces an O(n) size data structure such that the distance between s and any other point x in the plane (x) is not necessarily an obstacle vertex or a point on an obstacle edge) can be computed in O(1) time. The algorithm can also be used to compute shortest paths for the movement of a disk (so that optimal movement for arbitrary objects can be computed to the accuracy of enclosing them with the smallest possible disk).