A limit process for partial match queries in random quadtrees and 2-d trees
From MaRDI portal
Publication:389077
DOI10.1214/12-AAP912zbMath1358.68080arXiv1202.1342MaRDI QIDQ389077
Ralph Neininger, Nicolas Broutin, Henning Sulzbach
Publication date: 17 January 2014
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1202.1342
Analysis of algorithms (68W40) Combinatorial probability (60C05) Functional limit theorems; invariance principles (60F17) Data structures (68P05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (7)
On the cost of fixed partial match queries in \(K\)-d trees ⋮ A limit process for partial match queries in random quadtrees and 2-d trees ⋮ On the expected cost of partial match queries in random quad-\(K\)-d trees ⋮ Process convergence for the complexity of radix selection on Markov sources ⋮ A limit field for orthogonal range searches in two-dimensional random point search trees ⋮ The dual tree of a recursive triangulation of the disk ⋮ On a functional contraction method
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A limit process for partial match queries in random quadtrees and 2-d trees
- On the silhouette of binary search trees
- Branching processes in the analysis of the heights of trees
- Finite element mesh generation methods: A review and classification
- A fixed point theorem for distributions
- A structured computer system model
- Analytic variations on quadtrees
- Quad trees: A data structure for retrieval by composite keys
- A general limit theorem for recursive algorithms and combinatorial structures
- Partial match queries in relaxed multidimensional search trees
- On the analysis of stochastic divide and conquer algorithms
- Limit laws for partial match queries in quadtrees
- On the contraction method with degenerate limit equation.
- On a functional contraction method
- A functional limit theorem for the profile of search trees
- Foundations of multidimensional and metric data structures.
- Ignoring ignorance and agreeing to disagree
- On a multivariate contraction method for random recursive structures with applications to Quicksort
- Partial match queries in two-dimensional quadtrees: a probabilistic approach
- An Analysis of Randomd-Dimensional Quad Trees
- Rank Selection in Multidimensional Data
- Multidimensional binary search trees used for associative searching
- Partial-Match Retrieval Algorithms
- Partial Match Queries in Random Quadtrees
- On the average performance of orthogonal range search in multidimensional data structures
- Hypergeometrics and the cost structure of quadtrees
- Probability metrics and recursive algorithms
- Probability Inequalities for Sums of Bounded Random Variables
- A limit theorem for recursively defined processes in Lp
- Partial Match Queries in Random k-d Trees
- A limit theorem for “quicksort”
This page was built for publication: A limit process for partial match queries in random quadtrees and 2-d trees
