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 {{mvar|n}}, can be {{mvar|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 {{mvar|n}} and the number of reported points (often denoted {{mvar|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 {{math|O(n)}} (linear) space, and it handles queries in time {{math|O(log n + k)}} per query.