An Analysis of Randomd-Dimensional Quad Trees
- 1 October 1990
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 19 (5) , 821-832
- https://doi.org/10.1137/0219057
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
Keywords
This publication has 20 references indexed in Scilit:
- Applications of the theory of records in the study of random treesActa Informatica, 1988
- Branching processes in the analysis of the heights of treesActa Informatica, 1987
- A note on the height of binary search treesJournal of the ACM, 1986
- On Random Binary TreesMathematics of Operations Research, 1984
- Quintary treesACM Transactions on Database Systems, 1980
- Operations on Images Using Quad TreesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1979
- The complexity of finding fixed-radius near neighborsInformation Processing Letters, 1977
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952