A limit field for orthogonal range searches in two-dimensional random point search trees - Sorbonne Université Access content directly
Journal Articles Stochastic Processes and their Applications Year : 2019

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

Abstract

We consider the cost of general orthogonal range queries in random quadtrees. The cost of a givenquery is encoded into a (random) function of four variables which characterize the coordinates of twoopposite corners of the query rectangle. We prove that, when suitably shifted and rescaled, the randomcost function converges uniformly in probability towards a random field that is characterized as the uniquesolution to a distributional fixed-point equation. We also state similar results for2-d trees. Our resultsimply for instance that the worst case query satisfies the same asymptotic estimates as a typical query, andthereby resolve an open question of Chanzy, Devroye and Zamora-Cura [Acta Inf., 37:355–383, 2001]

Dates and versions

hal-02355899 , version 1 (08-11-2019)

Identifiers

Cite

Nicolas Broutin, Henning Sulzbach. A limit field for orthogonal range searches in two-dimensional random point search trees. Stochastic Processes and their Applications, 2019, 129 (8), pp.2912-2940. ⟨10.1016/j.spa.2018.08.014⟩. ⟨hal-02355899⟩
17 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More