Strong Convergence of Partial Match Queries in Random Quadtrees

DOI10.1017/S096354831200017XzbMath1252.68100arXiv1109.5579MaRDI QIDQ2911068

Nicolas Curien

Publication date: 12 September 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1109.5579

zbMATH Keywords

self-similar fragmentationsrandom recursive construction

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Martingales with continuous parameter (60G44) Self-similar stochastic processes (60G18) Information storage and retrieval of data (68P20) Limit theorems in probability theory (60F99) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (2)

On the number of large triangles in the Brownian triangulation and fragmentation processes ⋮ A limit field for orthogonal range searches in two-dimensional random point search trees

Cites Work

• Random recursive triangulations of the disk via fragmentation theory
• Analytic variations on quadtrees
• Quad trees: A data structure for retrieval by composite keys
• Asymptotic laws for nonconservative self-similar fragmentations
• Partial match queries in two-dimensional quadtrees: a probabilistic approach

This page was built for publication: Strong Convergence of Partial Match Queries in Random Quadtrees