DocumentCode
1960808
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
fYear
1988
fDate
7-10 Nov. 1988
Firstpage
530
Lastpage
533
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/ICCAD.1988.122564
Filename
122564
Link To Document