An Analysis of Random<i>d</i>-Dimensional Quad Trees

Luc Devroye, Louise Laforest

SIAM Journal on Computing · 1990 · 26 citations · 23 references

Concepts

Abstract

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.

References

23