Rectilinear Shortest Paths and Minimum Spanning Trees in the Presence of Rectilinear Obstacles
Authors:
- 1 March 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (3) , 321-331
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.Keywords
This publication has 23 references indexed in Scilit:
- Constructing the visibility graph for n-line segments in O(n2) timeInformation Processing Letters, 1985
- Euclidean shortest paths in the presence of rectilinear barriersNetworks, 1984
- On the X-Y convex hull of a set of X-Y polygonsBIT Numerical Mathematics, 1983
- Finding minimum rectilinear distance paths in the presence of barriersNetworks, 1981
- Two-Dimensional Voronoi Diagrams in the
L
p
-MetricJournal of the ACM, 1980
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979
- An O ( n log n ) Algorithm for Rectilinear Minimal Spanning TreesJournal of the ACM, 1979
- A shortest path algorithm for grid graphsNetworks, 1977
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- On the Shortest Spanning Subtree of a Graph and the Traveling Salesman ProblemProceedings of the American Mathematical Society, 1956