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, 223, American Mathematical Society Press, pp. 1–56.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.