The range 1 query (R1Q) problem

We define the range 1 query (R1Q) problem as follows. Given a d-dimensional (d≥1) input bit matrix A (consisting of 0's and 1's), preprocess A so that for any given region R of A, 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, axis-parallel right simplices 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.