Range Searching - Variations

Variations

There are several variations of the problem, and different data structures may be necessary for different variations. In order to obtain an efficient solution, several aspects of the problem need to be specified:

• Object types: Algorithms depend on whether S consists of points, lines, line segments, boxes, polygons... The simplest and most studied objects to search are points.

• Range types: The query ranges also need to be drawn from a predetermined set. Some well-studied sets of ranges, and the names of the respective problems are axis-aligned rectangles (orthogonal range searching), simplices (simplex range searching), halfspaces (halfspace range searching), and spheres/circles (spherical range searching / circular range searching).

• Query types: If the list of all objects that intersect the query range must be reported, the problem is called range reporting, and the query is called a reporting query. Sometimes, only the number of objects that intersect the range is required. In this case, the problem is called range counting, and the query is called a counting query. The emptiness query reports whether there is at least one object that intersects the range. In the semigroup version, a commutative semigroup (S,+) is specified, each point is assigned a weight from S, and it is required to report the semigroup sum of the weights of the points that intersect the range.

• Dynamic range searching vs. static range searching: In the static setting the set S is known in advance. In dynamic setting objects may be inserted or deleted between queries.

• Offline range searching: Both the set of objects and the whole set of queries are known in advance.