Analysis of the worst case space complexity of a PR quadtree

DOI10.1016/0020-0190(94)90065-5MaRDI QIDQ1318753zbMATH OpenOpenAlexFDO

Authors Sriram Pemmaraju, Clifford A. Shaffer

Publication date 5 April 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)90065-5

zbMATH Keywords

worst case analysishierarchical data structuresspatial data structurespoint dataPR quadtree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Recommendations

• Expected and worst-case storage requirements for quadtrees
• The space efficiency of quadtrees
• Expected worst-case partial match in random quadtries
• Faster compressed quadtrees
• Analytic variations on quadtrees

Cites work

• scientific article; zbMATH DE number 46317 (Why is no real title available?)
• An optimal boundary to quadtree conversion algorithm
• Expected and worst-case storage requirements for quadtrees
• Linear time distance transforms for quadtrees
• Neighbor finding techniques for images represented by quadtrees

Cited in

(4)

• Tight bounds in the quadtree complexity theorem and the maximal number of pixels crossed by a curve of given length
• Expected and worst-case storage requirements for quadtrees
• The space efficiency of quadtrees
• A primogenitary linked quad tree data structure and its application to discrete multiple criteria optimization

This page was built for publication: Analysis of the worst case space complexity of a PR quadtree

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