Sorted Range Reporting
Yakov Nekrich and Gonzalo Navarro
In this paper we consider a variant of the orthogonal range
reporting problem when all points should be reported in the sorted order
of their x-coordinates. We show that reporting two-dimensional points
with this additional condition can be organized (almost) as efficiently as
the standard range reporting.
Moreover, our results generalize and improve the previously known results
for the orthogonal range successor problem and can be used to
obtain better solutions for some stringology problems.