The range 1 query (R1Q) problem
From MaRDI portal
Publication:1659997
DOI10.1016/j.tcs.2015.12.040zbMath1398.68613MaRDI QIDQ1659997
Samuel McCauley, Pramod Ganapathi, Michael A. Bender, Yuan Tang, Rezaul Alam Chowdhury
Publication date: 23 August 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.12.040
circular; triangular; spherical; range query; orthogonal; rectangular; randomized; simplicial; polygonal; bit matrix; emptiness query; existential query; non-orthogonal; R1Q; range 1 query; range emptiness
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Entropy-bounded representation of point grids
- Space-efficient data-analysis queries on grids
- On space efficient two dimensional range minimum data structures
- Succinct data structures for flexible text retrieval systems
- Decomposable searching problems
- Surpassing the information theoretic bound with fusion trees
- Compressed suffix trees with full functionality
- Optimal lower bounds for rank and select indexes
- The Range 1 Query (R1Q) Problem
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Entropy-Bounded Representation of Point Grids
- Semialgebraic Range Reporting and Emptiness Searching with Applications
- Lower bounds for orthogonal range searching: I. The reporting case
- Lower bounds for orthogonal range searching: part II. The arithmetic model
- Two-Dimensional Range Minimum Queries
- Optimal Succinctness for Range Minimum Queries
- Rank/select operations on large alphabets
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- Efficient data structures for range searching on a grid
- Recursive Star-Tree Parallel Data Structure
- An improved data stream summary: the count-min sketch and its applications
- Orthogonal range searching on the RAM, revisited
- Lowest common ancestors in trees and directed acyclic graphs
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
