Rectilinear Path Problems among Rectilinear Obstacles Revisited
Rectilinear Path Problems among Rectilinear Obstacles Revisited
复制标题
重温直线障碍中的直线路径问题
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Chak
中科院分区：
文献类型：
--
作者：
Chung;D. T. Lee;Chak
提出了一种在一组直线障碍物中寻找两个给定点之间的直线无碰撞路径的有效算法。这些结果改善了以往求最短直线路、最小弯曲最短直线路、最短最小弯曲直线路和最小费用直线路的结果的时间复杂度。（mlog t+ tlog^{3/2} t）$运行时间，其中$t$是给定障碍物的极端边缘数，$m$是障碍物边缘数。在此基础上，得到了计算给定N个端点在直线障碍物间的L1最小生成树的O（NlogN+（m+N）logt+（t+N）log^2（t+N））算法.为了找到最小弯曲的最短路径，最短的最小弯曲的直线路径，和最小成本的直线路径，我们设计了一个新的动态搜索方法，并推导出算法，运行在$O（mlog^{3/2}m）$时间使用$O（mlog m）$空间或运行在$O（mlog^{2/2}m）$时间和空间。
Efficient algorithms are presented for finding rectilinear collision-free paths between two given points among a set of rectilinear obstacles. The results improve the time complexity of previous results for finding the shortest rectilinear path, the minimum-bend shortest rectilinear path, the shortest minimum-bend rectilinear path and the minimum-cost rectilinear path. For finding the shortest rectilinear path, a graph-theoretic approach is used and an algorithm is obtained with $O(mlog t+ tlog^{3/2} t)$ running time, where $t$ is the number of extreme edges of given obstacles and $m$ is the number of obstacle edges. Based on this result an $O(Nlog N+(m+N)log t + (t+N)log^2 (t+N))$ running time algorithm for computing the $L_1$ minimum spanning tree of given $N$ terminals among rectilinear obstacles is obtained. For finding the minimum-bend shortest path, the shortest minimum-bend rectilinear path, and the minimum-cost rectilinear path, we devise a new dynamic-searching approach and derive algorithms that run in $O(mlog^2m)$ time using $O(mlog m)$ space or run in $O(mlog^{3/2}m)$ time and space.