FINDING OBSTACLE-AVOIDING SHORTEST PATHS USING IMPLICIT CONNECTION GRAPHS

We introduce a framework for a class of algorithms solving shortest pa th related problems, such as the one-to-one shortest path problem, the one-to-many shortest paths problem and the minimum spanning tree prob lem, in the presence of obstacles. For these algorithms, the search sp ace is restricted to a sparse strong connection graph that is implicit ly represented and its searched portion is constructed incrementally o n-the-fly during search. The time and space requirements of these algo rithms essentially depend on actual search behavior. Therefore, additi onal techniques or heuristics can be incorporated into search procedur e to further improve the performance of the algorithms. These algorith ms are suitable for large VLSI design applications with many obstacles .