next up previous contents index CD CD Algorithms
Next: Point Location Up: Computational Geometry Previous: Nearest Neighbor Search

Range Search



Input description: A set S of n points in tex2html_wrap_inline30097 and a query region Q.

Problem description: Which points from S lie within Q?

Discussion: Range search problems arise in database and geographic information system (GIS) applications. Any data object with d numerical fields, such as person with height, weight, and income, can be modeled as a point in d-dimensional space. A range query describes a region in space and asks for all points or the number of points in the region. For example, asking for all people with income between $0 and $10,000, with height between 6'0'' and 7'0'', and weight between 50 and 140 lbs. defines a box containing people whose body and wallets are both thin.      

The difficulty of a range search problem depends on several factors:

Implementations: LEDA (see Section gif) provides excellent support for maintaining planar subdivisions in C++. In particular, it supports orthogonal range queries in tex2html_wrap_inline30109 time, where n is the complexity of the subdivision and k is the number of points in the rectangular region.   

Ranger is a tool for visualizing and experimenting with nearest-neighbor and orthogonal-range queries in high-dimensional data sets, using multidimensional search trees. Four different search data structures are supported by Ranger: naive kd-trees, median kd-trees, nonorthogonal kd-trees, and the vantage point tree. For each of these, Ranger supports queries in up to 25 dimensions under any Minkowski metric. It is available in the algorithm repository.   

A bare bones implementation in C of orthogonal range search using kd-trees appears in [GBY91]. Sedgewick [Sed92] provides code fragments of the grid method for orthogonal range search in C++. See Section gif for details on both of them.

Notes: Good expositions on data structures with worst-case tex2html_wrap_inline30111 performance for orthogonal-range searching [Wil85] include [PS85]. An exposition on kd-trees for orthogonal range queries in two dimensions appears in [PS85]. Their worst-case performance can be very bad; [LW77] describes an instance in two dimensions requiring tex2html_wrap_inline30113 time to report that a rectangle is empty.

The problem becomes considerably more difficult for nonorthogonal range queries, where the query region is not an axis-aligned rectangle. For half-plane intersection queries, tex2html_wrap_inline30115 time and linear space suffice [CGL85]; for range searching with simplex query regions (such as a triangle in the plane), lower bounds preclude efficient worst-case data structures. See [Yao90] for a discussion.  

Related Problems: Kd-trees (see page gif), point location (see page gif),    

next up previous contents index CD CD Algorithms
Next: Point Location Up: Computational Geometry Previous: Nearest Neighbor Search

Mon Jun 2 23:33:50 EDT 1997