In this work we present the average-case analysis of orthogonal range search for several multidimensional data structures. We first consider random relaxed K-d trees as a prototypical example and later
extend our results to several different multidimensional data structures. We show that the performance of range searches is related to the performance of a variant of partial matches which simplifies the
analysis and provides a tight asymptotic estimate for the expected cost of range searches.
Duch, A., Martinez, C. "On the average performance of orthogonal range search in multidimensional data structures". 2001.