INPUT OUTPUT

**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.

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 |

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