Finding obstacle-avoiding shortest path is an important problem in VLSI design, and connection graph is a fundamental tool to resolve the problem. The known best graph grounded on knowledge of free area, and it has O(t) vertices and O(tlogt) edges, in which t is the number of extreme edges of the obstacles. In this paper, a generalized connection graph GG is introduced, which is derived from some new conception such as generalized free area. GG is made up with vertex that represents the generalized free area and edges for their adjacency. It has only Θ(t) vertices and Θ(t) edges, and it is planar graph. An O(tlogt) time algorithm using plane scanning is designed to construct GG, and the do not change direction heuristic together with A* algorithm is used for getting the shortest obstacle-avoiding path using GG through the conception of formal path. This algorithm shorten the time complexity from O(tlogt)to Θ(t).
[1]Lee CY. An algorithm for path connections and its applications. IRE Transactions on Electronic Computers, 1961,EC-10:346~365.
[2]Akers SB. A modification of Lee's path connection algorithm. IEEE Transactions on Electronic Computers, 1967,EC-16:97~98.
[3]Soukup J. Fast maze router. In: Proceedings of the 15th Design Automation Conference. Las Vegas: ACM Press, 1978. 100~102.
[4]Hightower DW. A solution to line routing problems on the continuous plan. In: Proceedings of the 6th Annul Design Automation Workshop. ACM Press,1969. 1~24.
[5]Clarkson KL, Kapoor S, Vaidya PM. Rectilinear shortest path through polygonal obstacles in O(nlog2n) time. In: Proceedings of the 3rd Annual Symposium on Computational Geometry. New York: ACM Press, 1987. 251~257.
[7]Wu YF, Widmayer P, Schlag MDF, Wong CK. Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles. IEEE Transactions on Computers, 1987,36(3):321~331.
[8]Zhou Z. Obstacle-Avoiding minimum rectilinear steiner tree problem [MS. Thesis]. Hefei: University of Science and Technology of China, 1998 (in Chinese with English Abstract).
[9]Zhou Z, Chen GL, Gu J. Finding obstacle-avoiding shortest path using connection graph with O(tlogt) edges. Chinese Journal of Computers, 1999,22(5):519~524 (in Chinese with English Abstract).