solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3244次
A limit field for orthogonal range searches in two-dimensional random point search trees. (arXiv:1711.11354v1 [math.PR])
来源于:arXiv
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.
Our results imply for instance that the worst case query satisfies the same
asymptotic estimates as a typical query, and thereby resolve an old question of
Chanzy, Devroye and Zamora-Cura [\emph{Acta Inf.}, 37:355--383, 2000] 查看全文>>