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.7 Point Location

Problem Input | Problem Output

INPUT                    OUTPUT

Input Description: A decomposition of the plane into polygonal regions, and a query point q.

Problem: Which region contains the query point q?

Excerpt from The Algorithm Design Manual: Point location is a fundamental subproblem in computational geometry, usually needed as an ingredient to solve larger geometric problems. In a dispatch system to assign policemen to the scene of a crime, the city will be partitioned into different precincts or districts. Given a map of regions and a query point (the crime scene), the system must identify which region contains the point. This is exactly the problem of planar point location.


  • 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)
  • Arrange - maintainance of arrangements with point location (C) (rating 5)
  • 3D Convex Hull algorithm in Java (C) (rating 3)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 2)

  • Recommended Books

    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 Algorithms from P to NP, Vol. I: Design and Efficiency by B. Moret and H. Shapiro
    Introduction to Algorithms by U. Manber Computational Geometry by F. Preparata and M. Shamos

    Related Problems

    Maintaining Line Arrangements
    Nearest Neighbor Search
    Range Search
    Voronoi Diagrams

    This page last modified on 2008-07-10 .