A probabilistic analysis of hierarchical geometric data structures

摘要

The size of five hierarchical geometric data structures isinvestigated analytically using random image models. Upper bounds andsome lower bounds on the size of the structures are derived. The resultsare useful in predicting the storage required by the structures as wellas the performance of algorithms that rely on them