ADAPTABLE QUAD TREE TECHNIQUES

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.