Entropy-bounded representation of point grids

DOI10.1016/J.COMGEO.2013.08.002MaRDI QIDQ390358zbMATHOpenAlexFDO

Authors Arash Farzan, Travis Gagie, Gonzalo Navarro

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

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

Recommendations

• Entropy-bounded representation of point grids
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Compact and succinct data structures for multidimensional orthogonal range searching
• Faster compressed quadtrees
• Compressed data structures for range searching

Cites work

• scientific article; zbMATH DE number 5485435 (Why is no real title available?)
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 6297698 (Why is no real title available?)
• Cell probe lower bounds for succinct data structures
• Cell-probe lower bounds for succinct partial sums
• Compressed data structures: Dictionaries and data-aware measures
• Data structures for range minimum queries in multidimensional arrays
• Entropy-bounded representation of point grids
• Filtering Search: A New Approach to Query-Answering
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Low redundancy in static dictionaries with constant query time
• Lower bounds for orthogonal range searching: I. The reporting case
• More haste, less waste: lowering the redundancy in fully indexable dictionaries
• On the Redundancy of Succinct Data Structures
• On the Size of Succinct Indices
• Optimal indexes for sparse bit vectors
• Optimal lower bounds for rank and select indexes
• Orthogonal range searching on the RAM, revisited
• Practical entropy-compressed rank/select dictionary
• Recursive Star-Tree Parallel Data Structure
• Space efficient dynamic orthogonal range reporting
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Time-space trade-offs for predecessor search

Cited in

(6)

• Grid-entropy-based boundary points detecting algorithm
• The range 1 query (R1Q) problem
• Compact and succinct data structures for multidimensional orthogonal range searching
• Scale Space and PDE Methods in Computer Vision
• Entropy-bounded representation of point grids
• The m-dimensional grid point space

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

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