SIAM Journal on Computing · 1990 · 26 citations · 23 references
ComputingComputer ScienceComputational GeometryGeometric ModelingProbability TheoryProbabilistic CombinatoricsTree FormQuadtreesRandom Trees
It is shown that the depth of the last node inserted in a random quad tree constructed from independent uniform $[0,1]^d $ random vectors is in probability asymptotic to $({2 / d}) \log n$, where log denotes the natural logarithm. In addition, for $d = 2$, exact values are obtained for all the moments of the depth of the last node.
23
Multidimensional binary search trees used for associative searching
Jon Bentley · Communications of the ACM · 1975 · 7.5K citations · Full text