Range reporting

In computational geometry and database theory, a range reporting query asks for a list of the points that match the query.

The query is often specified by a geometric shape, containing all the points that should match, and is called a range.

Range reporting queries are often handled by building a data structure from a collection of points that can answer queries efficiently.

Because the worst case output size for a range reporting query, measured as a function of the data set size n, can be n itself, much of the research on range reporting data structures has investigated output-sensitive algorithms, where the query time is analyzed in terms of both n and the number of reported points (often denoted k).

For example, for one-dimensional (numeric) data with query ranges that are intervals, range reporting queries can be handled by storing the data in a sorted array.