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.

The best books available for this problem are Computational Geometry in C by Joseph O'Rourke and Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf.


Implementations

  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)
  • Arrange - maintainance of arrangements with point location (C) (rating 6)
  • 3D Convex Hull algorithm in Java (C) (rating 3)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 3)

    Related Problems

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


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .