Rectilinear Shortest Paths and Minimum Spanning Trees in the Presence of Rectilinear Obstacles

Abstract

We Study The Rectilinear Shortest Paths And Minimum Spanning Tree (Mst) Problems For A Set Of Points In The Plane In The Presence Of Rectilinear Obstacles. We Use The Track Graph, A Suitably Defined Grid-like structure, to obtain efficient solutions for both problems. The track graph consists of rectilinear tracks defined by the obstacles and the points for which shortest paths and a minimum spanning tree are sought. We use a growth process like Dijkstra's on the track graph to find shortest paths from any point in the set to all other points (the one-to-all shortest paths problem). For the one-to-all shortest paths problem for n points we derive an O(n min {log n, log e} + (e + k) log t) time algorithm, where e is the total number of edges of all obstacles, t is the number of extreme edges of all obstacles, and k is the number of intersections among obstacle tracks (all bounds are for the worst case). The MST for the points is constructed also in time O(n log n + (e + k) log t) by a hybrid method of searching for shortest paths while simultaneously constructing an MST. An interesting application of the MST algorithm is the approximation of Steiner trees in graphs. Copyright © 1987 by The Institute of Electrical and Electronics Engineers, Inc.