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.


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)
  • 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


      
    Kd-Trees
      
    Maintaining Line Arrangements
      
    Nearest Neighbor Search
      
    Range Search
      
    Voronoi Diagrams



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