A limit field for orthogonal range searches in two-dimensional random point search trees

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:129

Article

Broutin, Nicolas¹  Sulzbach, Henning² 

[1] Sorbonne Univ, Campus Pierre & Marie Curie Case Courrier 158, F-75252 Paris 05, France

[2] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England

关键词: Quadtree;    Random partition;    Convergence in distribution;    Contraction method;    Range query;    Partial match;    Analysis of algorithms;   

DOI  :  10.1016/j.spa.2018.08.014

来源: Elsevier

【 摘 要 】

We consider the cost of general orthogonal range queries in random quadtrees. The cost of a given query is encoded into a (random) function of four variables which characterize the coordinates of two opposite corners of the query rectangle. We prove that, when suitably shifted and rescaled, the random cost function converges uniformly in probability towards a random field that is characterized as the unique solution to a distributional fixed-point equation. We also state similar results for 2-d trees. Our results imply for instance that the worst case query satisfies the same asymptotic estimates as a typical query, and thereby resolve an open question of Chanzy et al. (2001). (C) 2018 Elsevier B.V. All rights reserved.

【 授权许可】

Free