Partial Match Queries in Two-Dimensional Quadtrees: a Probabilistic Approach
Curien, Nicolas · Joseph, Adrien
Original · EN
We analyze the mean cost of the partial match queries in random two-dimensional quadtrees. The method is based on fragmentation theory. The convergence is guaranteed by a coupling argument of Markov chains, whereas the value of the limit is computed as the fixed point of an integral equation.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.