spatial data structures can also be used to store line objectrectangle objector objects of arbitrary shape (such as polygons in two dimensions or polyhedra in three dimensionsa simpleyet effectivedata structure for storing rectangles or arbitrary polygonal shapes can be derived from the pr quadtree pick threshold value cand subdivide any region into four quadrants if it contains more than objects special case must be dealt with when more than object intersect some of the most interesting developments in spatial data structures have to do with adapting them for disk-based applications howeverall such disk-based implementations boil down to storing the spatial data structure within some variant on either -trees or hashing further reading patricia tries and other trie implementations are discussed in information retrievaldata structures algorithmsfrakes and baeza-yateseds [fby see knuth [knu for discussion of the avl tree for further reading on splay treessee "self-adjusting binary searchby sleator and tarjan [st the world of spatial data structures is rich and rapidly evolving for good introductionsee foundations of multidimensional and metric data structures by hanan samet [sam this is also the best reference for more information on the pr quadtree the - tree was invented by john louis bentley for further information on the - treein addition to [sam ]see [ben for information on using quadtree to store arbitrary polygonal objectssee [sh for discussion on the relative space requirements for two-way versus multiway branchingsee " generalized comparison of quadtree and bintree storage requirementsby shafferjuvvadiand heath [sjh closely related to spatial data structures are data structures for storing multidimensional data (which might not necessarily be spatial in naturea popular data structure for storing such data is the -treewhich was originally proposed by guttman [gut exercises show the binary trie (as illustrated by figure for the following collection of values show the pat trie (as illustrated by figure for the following collection of values write the insertion routine for binary trie as shown in figure write the deletion routine for binary trie as shown in figure