A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES
Yakov Nekrich · International Journal of Computational Geometry & Applications · 2009
In this paper we present a linear space dynamic data structure for two-dimensional orthogonal range reporting and emptiness queries. This data structure answers range reporting queries in time [Formula: see text] for any ε > 0 and k the size of the answer. Our data structure also supports emptiness and one-reporting queries in time O( log n log log n). The model of computation used in this paper is a unit-cost RAM model.