Paths through a maze of rectangles
- 1 July 1992
- Vol. 22 (4) , 349-367
- https://doi.org/10.1002/net.3230220404
Abstract
Finding short paths through mazes of rectangles has applications in VLSI wire‐routing and robotics. This paper introduces and analyzes heuristic algorithms for finding short paths, under the assumption that the algorithms have no information about rectangles not already encountered along a path. Tight worst‐case bounds are derived for the ratio of the length of these algorithms' paths to the lengths of shortest paths. A model of random mazes is defined for testing the typical or average‐case behavior of algorithms. Although specially designed mazes can force the heuristic algorithms to give long paths, simulations and analysis show that the better heuristics usually give paths nearly as short as possible.Keywords
This publication has 5 references indexed in Scilit:
- Rectilinear shortest paths in the presence of rectangular barriersDiscrete & Computational Geometry, 1989
- Time Redundant Fault-Location in Bit-Sliced ALU'sIEEE Transactions on Computers, 1987
- Rectilinear Shortest Paths and Minimum Spanning Trees in the Presence of Rectilinear ObstaclesIEEE Transactions on Computers, 1987
- Rectilinear shortest paths through polygonal obstacles in O(n(logn)2) timePublished by Association for Computing Machinery (ACM) ,1987
- Finding minimum rectilinear distance paths in the presence of barriersNetworks, 1981