An Analysis of Randomd-Dimensional Quad Trees

DOI10.1137/0219057zbMath0711.68032OpenAlexW2026409183MaRDI QIDQ3495638

Louise Laforest, Luc P. Devroye

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219057

zbMATH Keywords

analysis of algorithmsprobability inequalitiessearch treemultidimensional data structuresaverage time analysisexpected behaviorrandom quad tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items (12)

Combinatorial variations on multidimensional quadtrees ⋮ On the distribution of the arity of the root of a \(d\)-dimensional quadtree ⋮ Study of the universal constants for the multidimensional search quadtrees ⋮ A limit process for partial match queries in random quadtrees and 2-d trees ⋮ Hypergeometrics and the cost structure of quadtrees ⋮ Page usage in a quadtree index ⋮ On a multivariate contraction method for random recursive structures with applications to Quicksort ⋮ A limit field for orthogonal range searches in two-dimensional random point search trees ⋮ Width and mode of the profile for some random trees of logarithmic height ⋮ On the internal path length ofd-dimensional quad trees ⋮ Universal Limit Laws for Depths in Random Trees ⋮ Analytic variations on quadtrees

This page was built for publication: An Analysis of Randomd-Dimensional Quad Trees