Comparisons of quad trees and 4-D trees: new results (VLSI layout)

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. >