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.