Combinatorial variations on multidimensional quadtrees

DOI10.1016/0097-3165(95)90103-5MaRDI QIDQ1344226zbMATH OpenOpenAlexFDO

Authors Gilbert Labelle, Louise Laforest

Publication date 11 June 1995

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(95)90103-5

zbMATH Keywords

asymptotic formulasquadtreesspecies

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Random graphs (graph-theoretic aspects) (05C80) Algebraic combinatorics (05E99) Graph theory (including graph drawing) in computer science (68R10)

Review text

The quadtrees were introduced by \textit{A. F. Finkel} and \textit{J. L. Bentley} [Acta Inform. 4, 1-9 (1974; Zbl 0278.68030)] and \textit{H. Samet} [Comput. Surveys 16, 187-260 (1984)] as a generalization of binary search trees. The authors present a parallel study of three models of multidimensional quadtrees---quadtrees of Catalan's type, increasing quadtrees and point quadtrees, using the language of the theory of species. Combinatorial equations for these structures are obtained that lead to explicit, recursive and asymptotic formulas for the probability of having \(k\) nodes in a fixed hyperoctant, the expected value and the variance of the number of leaves.

Recommendations

• Analytic variations on quadtrees
• On the size of quadtrees generalized to d-dimensional binary pictures
• Study of the universal constants for the multidimensional search quadtrees
• An Analysis of Randomd-Dimensional Quad Trees
• Around the root of random multidimensional quadtrees

Cites work

• An Analysis of Randomd-Dimensional Quad Trees
• Analytic variations on quadtrees
• scientific article; zbMATH DE number 3884234 (Why is no real title available?)
• scientific article; zbMATH DE number 3864449 (Why is no real title available?)
• scientific article; zbMATH DE number 4025850 (Why is no real title available?)
• scientific article; zbMATH DE number 3728625 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• Page usage in a quadtree index
• Quad trees: A data structure for retrieval by composite keys
• The Expected Distribution of Degrees in Random Binary Search Trees
• Une nouvelle demonstration combinatoire des formules d'inversion de Lagrange

Cited in

(14)

• Noncommutative algebra, multiple harmonic sums and applications in discrete probability
• On the size of quadtrees generalized to d-dimensional binary pictures
• Analytic variations on quadtrees
• X-trees and weighted quartet systems
• On the distribution of the arity of the root of a d-dimensional quadtree
• Study of the universal constants for the multidimensional search quadtrees
• scientific article; zbMATH DE number 2127736 (Why is no real title available?)
• Around the root of random multidimensional quadtrees
• scientific article; zbMATH DE number 5562391 (Why is no real title available?)
• Set operations on linear quadtrees
• Euler Sums and Contour Integral Representations
• Special values of multiple polylogarithms
• On the inner structure of multidimensional simply generated trees
• Hypergeometrics and the cost structure of quadtrees

Describes a project that uses

Uses Software

• Maple

This page was built for publication: Combinatorial variations on multidimensional quadtrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1344226)