The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.6.6 Range Search

Problem Input | Problem Output

INPUT                    OUTPUT

Input Description: A set S of n points in E^d, and a query polygon Q.

Problem: Which points from S lie within Q?

Excerpt from The Algorithm Design Manual: 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.

Implementations

  • CGAL: The Computational Geometry Algorithms Library (C++) (rating 8)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 8)
  • ANN - Approximate Nearest Neighbors (C++) (rating 7)
  • Ranger - Nearest Neighbor Search in Higher Dimensions (C) (rating 4)
  • Algorithms in C++ -- Sedgewick (C++) (rating 3)
  • Handbook of Algorithms and Data Structures (C,Pascal) (rating 2)

    • Recommended Books

    Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf Computational Geometry in C by Joseph O'Rourke
    Handbook of Algorithms and Data Structures by G. Gonnet and R. Baeza-Yates Computational Geometry by F. Preparata and M. Shamos

    Related Problems
    Kd-Trees
    Nearest Neighbor Search
    Point Location


    This page last modified on 2008-07-10 .
    www.algorist.com