Entropy-bounded representation of point grids

DOI10.1016/j.comgeo.2013.08.002zbMath1280.65024OpenAlexW2142792592MaRDI QIDQ390358

Travis Gagie, Gonzalo Navarro, Arash Farzan

Publication date: 8 January 2014

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2013.08.002

zbMATH Keywords

complexitycompressed data structuresrange queriesrange countinggeometric gridspoint selection queriesrange reporting

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Related Items (2)

The range 1 query (R1Q) problem ⋮ Compact and succinct data structures for multidimensional orthogonal range searching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal indexes for sparse bit vectors
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Compressed data structures: Dictionaries and data-aware measures
• Optimal lower bounds for rank and select indexes
• Low Redundancy in Static Dictionaries with Constant Query Time
• Time-space trade-offs for predecessor search
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Entropy-Bounded Representation of Point Grids
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Lower bounds for orthogonal range searching: I. The reporting case
• On the Redundancy of Succinct Data Structures
• On the Size of Succinct Indices
• Filtering Search: A New Approach to Query-Answering
• Recursive Star-Tree Parallel Data Structure
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Practical Entropy-Compressed Rank/Select Dictionary
• Space efficient dynamic orthogonal range reporting
• More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
• Orthogonal range searching on the RAM, revisited
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting

This page was built for publication: Entropy-bounded representation of point grids