Tight space bounds for two-dimensional approximate range counting

DOI10.1145/3205454MaRDI QIDQ4554350zbMATH OpenOpenAlexWikidataFDO

Authors Zhewei Wei, Ke Yi

Publication date 13 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3205454

zbMATH Keywords

data structuresdiscrepancy theoryrange counting

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• The space complexity of 2-dimensional approximate range counting
• Data structures for approximate orthogonal range counting
• Adaptive and approximate orthogonal range counting
• Adaptive and approximate orthogonal range counting
• Approximate range searching

Cited in

(6)

• Data structures for approximate orthogonal range counting
• Approximate range counting revisited
• Distribution-sensitive bounds on relative approximations of geometric ranges
• The space complexity of 2-dimensional approximate range counting
• scientific article; zbMATH DE number 7740901 (Why is no real title available?)
• On space efficient two dimensional range minimum data structures

This page was built for publication: Tight space bounds for two-dimensional approximate range counting

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