RECTILINEAR PATH PROBLEMS AMONG RECTILINEAR OBSTACLES REVISITED

摘要

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(m log t + t log(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(N log 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(m log(2) m) time using O(m log m) space or run in O(m log(3/2) m) time and space. [References: 18]