Analytic variations on quadtrees

DOI10.1007/BF01891833zbMath0783.68056MaRDI QIDQ1310465

Philippe Flajolet, Claude Puech, Gaston H. Gonnet, John Michael Robson

Publication date: 20 March 1994

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

generating functionshypergeometric functionslinear recurrencesquadtreesmultidimensionalfully specified searchmultidimensional searchingpartial-match queriessingularity analysis techniques

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items

Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform, Limit laws for partial match queries in quadtrees, Combinatorial variations on multidimensional quadtrees, On the distribution of the arity of the root of a \(d\)-dimensional quadtree, Strong Convergence of Partial Match Queries in Random Quadtrees, Study of the universal constants for the multidimensional search quadtrees, An improved master theorem for divide-and-conquer recurrences, A limit process for partial match queries in random quadtrees and 2-d trees, Hypergeometrics and the cost structure of quadtrees, Quad-\(k\mathrm d\) trees: a general framework for \(k\mathrm d\) trees and quad trees, Fixed Partial Match Queries in Quadtrees, Partial match queries in two-dimensional quadtrees: a probabilistic approach, Page usage in a quadtree index, Singularity analysis, Hadamard products, and tree recurrences, On a multivariate contraction method for random recursive structures with applications to Quicksort, A limit field for orthogonal range searches in two-dimensional random point search trees, Width and mode of the profile for some random trees of logarithmic height, On the internal path length ofd-dimensional quad trees, Partial match queries in random quadtrees, The dual tree of a recursive triangulation of the disk, Psi-series method for equality of random trees and quadratic convolution recurrences, On a functional contraction method

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gaussian limiting distributions for the number of components in combinatorial structures
• Asymptotic expansions for the coefficients of analytic generating functions
• Analysis of grid file algorithms
• Resurrecting the asymptotics of linear recurrences
• Branching processes in the analysis of the heights of trees
• A holonomic systems approach to special functions identities
• Page usage in a quadtree index
• Analysis of range searches in quad trees
• On the average number of maximal in a set of vectors
• Ignoring ignorance and agreeing to disagree
• An Analysis of Randomd-Dimensional Quad Trees
• Singularity Analysis of Generating Functions
• Exact and asymptotic distributions in digital and binary search trees
• Multidimensional binary search trees used for associative searching