Multiple Storage Quad Trees: A Simpler Faster Alternative to Bisector List Quad Trees

A bisector list quad tree is a quad tree which stores objects intersecting more than one quad on horizontal and vertical bisector lists. This is the form of quad tree originally proposed by Kedem for organizing boxes and polygons in a plane so that one can quickly find the objects intersecting an arbitrary window. A multiple storage quad tree is a quad tree which stores pointers to objects intersecting more than one quad in all of the quads that they intersect. This paper describes and analyzes multiple storage quad trees. It is shown that multiple storage quad trees can be efficient in storage space, often using less than 25 percent more space than a simple list of the objects. That is, the tree nodes and other pointers combined often use less than 25 percent of the space needed to store the object descriptions. It is also shown that using multiple-storage quad trees makes possible very rapid searches for the objects intersecting a small window. In most cases fewer than 10 nodes must be examined per object found in the window. Finally, multiple storage quad trees and the algorithms which operate on them are found to be very simple and intuitive.