@inproceedings{d49c1fdd8a6a43a39652267f5ba03481,
title = "The range 1 query (R1Q) problem",
abstract = "We define the range 1 query (R1Q) problem as follows. Given a d-dimensional (d≥1) input bit matrix A, preprocess A so that for any given region R of A, one can efficiently answer queries asking if R contains a 1 or not. We consider both orthogonal and non-orthogonal shapes for R including rectangles, axis-parallel right-triangles, certain types of polygons, and spheres. We provide space-efficient deterministic and randomized algorithms with constant query times (in constant dimensions) for solving the problem in the word RAM model. The space usage in bits is sublinear, linear, or near linear in the size of A, depending on the algorithm.",
keywords = "circular, non-orthogonal, orthogonal, polygonal, R1Q, randomized, range emptiness, range query, rectangular, spherical, triangular",
author = "Bender, \{Michael A.\} and Chowdhury, \{Rezaul A.\} and Pramod Ganapathi and Samuel McCauley and Yuan Tang",
year = "2014",
doi = "10.1007/978-3-319-08783-2\_11",
language = "English",
isbn = "9783319087825",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "116--128",
booktitle = "Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings",
note = "20th International Computing and Combinatorics Conference, COCOON 2014 ; Conference date: 04-08-2014 Through 06-08-2014",
}