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 is a special case of range searching, in which queries may return other kinds of aggregate information about points in 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. With this structure, one can use binary search to find the point closest to the start of a query interval, and then scan the array from that point forwards to list all of the points in the interval. Storing this data structure uses O(n) (linear) space, and it handles queries in time O(log n + k) per query.

References

• Agarwal, P. K.; Erickson, J. (1999), "Geometric Range Searching and Its Relatives" (PDF), in Chazelle, Bernard; Goodman, Jacob; Pollack, Richard (eds.), Advances in Discrete and Computational Geometry: proceedings of the 1996 AMS-IMS-SIAM joint summer research conference, Discrete and Computational Geometry—Ten Years Later, July 14-18, 1996, Mount Holyoke College, Contemporary Mathematics, vol. 223, American Mathematical Society Press, pp. 1–56.