Title :
Two-layer quad trees: a data structure for high-speed interactive layout tools
Author :
Li Wanhao ; Legendre, S. ; Gardiner, K.
Author_Institution :
Motorola Inc., Chandler, AZ, USA
Abstract :
A two-layer quad tree data structure which creates an effective search environment for both region queries and size queries is described. A corner-based sorting method resolves the quad tree bisector list problem. A region-growing technique reduces region query search overhead. A two-layer quad tree implementation improves size-query speed. Experimental results show that these techniques significantly improve query speed for both classes of queries.<>
Keywords :
circuit layout CAD; data structures; search problems; trees (mathematics); corner-based sorting method; data structure; high-speed interactive layout tools; quad tree bisector list problem; quadtree data structure; query speed; region queries; region-growing technique; search environment; search overhead; size queries; two-layer quad tree data structure; Binary search trees; Binary trees; Circuits; Degradation; Displays; Memory management; Multidimensional systems; Sorting; Tree data structures; Very large scale integration;
Conference_Titel :
Computer-Aided Design, 1988. ICCAD-88. Digest of Technical Papers., IEEE International Conference on
Conference_Location :
Santa Clara, CA, USA
Print_ISBN :
0-8186-0869-2
DOI :
10.1109/ICCAD.1988.122564
