Title :
Comparisons of quad trees and 4-D trees: new results [VLSI layout]
Author :
Pitaksanonkul, Anucha ; Thanawastien, Suchai ; Lursinsap, Chidchanok
Author_Institution :
Center for Adv. Comput. Studies, Southwestern Louisiana Univ., Lafayette, LA, USA
fDate :
11/1/1989 12:00:00 AM
Abstract :
A comparison is made between two tree data structures that support region queries for VLSI layout systems. In a previous study, J.B. Rosenberg (ibid., vol.CAD-4, no.1, p.53-67, 1985) demonstrated that four-dimensional trees have a faster speed but use more memory space than quad trees with bisector lists. In this study the authors show that quad trees without bisector lists, for some small threshold values, have a better speed and require less storage than four-dimensional trees
Keywords :
VLSI; circuit layout CAD; data structures; integrated circuit technology; network topology; trees (mathematics); 4D trees; CAD; IC design; VLSI layout systems; four-dimensional trees; quad trees; region queries; tree data structures; Circuits; Computer science education; Data mining; Design automation; Grid computing; Organizing; Routing; Tree data structures; Very large scale integration;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
