Page usage in a quadtree index

This paper provides a characterization of the storage needs of a quadtree when used as an index to access large volumes of 2-dimensional data. It is shown that the page occupancy for data in random order approaches 33%. A precise mathematical analysis that involves a modicum of hypergeometric functions and dilogarithms, together with some computer algebra is presented.A brief survey of the analysis of storage usage in tree structures is included. The 33% ratio for quadtrees is to be compared to the figures for binary search trees (50%), tries (69%), and quadtries (46%).The research of this author was done while visiting INRIA, Rocquencourt, France under support from the Ministry of Education of Japanese Government.Work of this author was supported in part by the Basic Research Action of the E.C. under contract No. 3075 (Project ALCOM).