Strong convergence of partial match queries in random quadtrees

2011/09/26 by Nicolas Curien, Curien, Nicolas
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DS #math.PR

paper · pdf · doi:10.48550/arxiv.1109.5579

11 pages, 4 figures

arxiv created 2011/09/26 · arxiv updated 2011/09/27

Abstract

We prove that the rescaled costs of partial match queries in a random two-dimensional quadtree converge almost surely towards a random limit which is identified as the terminal value of a martingale. Our approach shares many similarities with the theory of self-similar fragmentations.

Related

• Partial Match Queries in Two-Dimensional Quadtrees : a Probabilistic Approach
• Partial match queries in random quadtrees
• A limit field for orthogonal range searches in two-dimensional random point search trees
• The Minimum Perfect Matching in Pseudo-dimension 0
• Martingales and Profile of Binary Search Trees