 |
 |
|
|
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.
  Kd-Trees |
  Maintaining Line Arrangements |
  Nearest Neighbor Search |
  Range Search |
  Voronoi Diagrams |
As an Amazon affiliate, I earn from qualifying purchases if you buy from links on this website.
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