computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

and

database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...

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 search In computer science, the range searching problem consists of processing a set ''S'' of objects, in order to determine which objects from ''S'' intersect with a query object, called the ''range''. For example, if ''S'' is a set of points correspond ...

ing, 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 In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...

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 , can be itself, much of the research on range reporting data structures has investigated

output-sensitive algorithm In computer science, an output-sensitive algorithm is an algorithm whose running time depends on the size of the output, instead of, or in addition to, the size of the input. For certain problems where the output size varies widely, for example fro ...

s, where the query time is analyzed in terms of both and the number of reported points (often denoted ). For example, for one-dimensional (numeric) data with query ranges that are

intervals Interval may refer to: Mathematics and physics * Interval (mathematics), a range of numbers ** Partially ordered set#Intervals, its generalization from numbers to arbitrary partially ordered sets * A statistical level of measurement * Interval est ...

, range reporting queries can be handled by storing the data in a sorted array. With this structure, one can use

binary search In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...

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 (linear) space, and it handles queries in time per query.

References

*{{citation, first1=P. K., last1=Agarwal, author1-link=Pankaj K. Agarwal, first2=J., last2=Erickson, year=1999, contribution=Geometric Range Searching and Its Relatives, title=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, series=Contemporary Mathematics, volume=223, publisher=American Mathematical Society Press, pages=1–56, editor1-first=Bernard, editor1-last=Chazelle, editor1-link=Bernard Chazelle, editor2-first=Jacob, editor2-last=Goodman, editor2-link=Jacob E. Goodman, editor3-first=Richard, editor3-last=Pollack, contribution-url=http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/survey.pdf. Geometric data structures Database theory