Publication
IEEE TC
Paper

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

View publication

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.

Date

Publication

IEEE TC

Authors

Share