The range 1 query (R1Q) problem

DOI10.1016/J.TCS.2015.12.040zbMath1398.68613OpenAlexW2228479156MaRDI 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

zbMATH Keywords

circulartriangularsphericalrange queryorthogonalrectangularrandomizedsimplicialpolygonalbit matrixemptiness queryexistential querynon-orthogonalR1Qrange 1 queryrange emptiness

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Uses Software

• Pochoir

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

This page was built for publication: The range 1 query (R1Q) problem