Title: ADAPTABLE QUAD TREE TECHNIQUES
Authors: SU, SJ
KUO, YS
TSAY, JC
資訊工程學系
Department of Computer Science
Keywords: MULTIPLE STORAGE QUAD TREE;QUAD TREE;REGION QUERY;VLSI LAYOUT
Issue Date: 1-Jul-1993
Abstract: The quad tree is a widely used data structure for region queries. Quad trees normally perform reasonably efficient on the majority of layout data, but could perform very poor on certain extreme data. This demonstrates the quad tree's deficiency in its adaptability to peculiar layout data. We address two aspects of the adaptability problem. On the one hand, the threshold of a quad tree is allowed to change in order to match the global complexity of the layout. On the other hand, a new quad subdivision criterion is developed which adapts a quad tree to the nonuniform distribution of objects with various sizes. Experiments have indicated that the two techniques are indeed useful in coping with the peculiarity of extreme layout data.
URI: http://hdl.handle.net/11536/2958
ISSN: 0167-9260
Journal: INTEGRATION-THE VLSI JOURNAL
Volume: 15
Issue: 1
Begin Page: 51
End Page: 71
Appears in Collections:Articles