The rectilinear shortest path problem can be stated as follows: given a set of m non-intersecting simple polygonal obstacles in the plane, find a shortest LI-metric (rectilinear)path from a point s to a point t that avoids all the obstacles. The path can touch anobstacle but does not cross it. This paper presents an algorithm with time complexity0(n + m(Ign)~(3/2)), which is close to the known lower bound of Ω(n +m lgm) for findingsuch a path. Here, n is the number of vertices of all the obstacles together.
展开▼
机译：直线最短路径问题可以描述如下：给定平面中有m个不相交的简单多边形障碍物，找到从点s到点t的最短LI-metric（直线）路径，可以避开所有障碍物。路径可以碰到障碍物，但不能穿过障碍物。本文提出了一种时间复杂度为0（n + m（Ign）〜（3/2））的算法，该算法接近于已知的Ω（n + m lgm）的下界来寻找这样的路径。在此，n是所有障碍物的顶点总数。
展开▼
