Approximate range counting revisited
Saladi Rahul · DOAJ (DOAJ: Directory of Open Access Journals) · 2021
We study range-searching for colored objects, where one has to count (approxi- mately) the number of colors present in a query range. The problems studied mostly involve orthogonal range-searching in two and three dimensions, and the dual setting of rectangle stabbing by points. We present optimal and near-optimal solutions for these problems. Most of the results are obtained via reductions to the approximate uncolored version, and improved data-structures for them. An additional contribution of this work is the introduction of nested shallow cuttings.