Stony Brook Algorithm Repository


Point Location

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 (rating 8)
LEDA (rating 8)
ANN (rating 7)
go-rquad (rating 5)
point-location (rating 5)
Arrange (rating 5)
3D Convex Hull algorithm in Java (rating 3)
Moret and Shapiro's Algorithms P to NP (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

Go To Main Page