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.

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.