Point Location

Open any map app, tap a point on the screen and the app instantly tells you which country, county or postal district you're in. That instant answer rests on a solved algorithmic problem called point location.

The setting is a planar subdivision: the plane divided into a finite number of non-overlapping regions by straight-line edges. Think of a country map cut into states, a city cut into neighborhoods, or a game world cut into zones. Given any query point q, point location asks: which region contains q?

Naive search scans every region and tests whether q is inside — $O(*n*)$ per query. For a one-off question that is fine. But a GIS system or game engine issues millions of queries against the same fixed map. With the right preprocessing the answer drops to $O(\log *n*)$ per query — the same asymptotic cost as looking up a name in a sorted phone book — no matter how complex the map.

The canvas below is divided into colored regions by a small planar subdivision. Click anywhere — the algorithm identifies the containing region instantly by navigating a prebuilt search structure.

<p class="hint">{{hint}}</p>
<canvas id="canvas" width="480" height="300"></canvas>
<div class="status" id="status">{{status_init}}</div>
<div class="info" id="info"></div>
<div class="btns">
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; cursor: crosshair; width: 100%; max-width: 480px; touch-action: none; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.found { color: #0a7d33; }
.status.none { color: #c92f3c; }
.info { font-size: .85rem; color: #555; margin-bottom: .4rem; min-height: 1.2em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Behind the button the demo walks a slab decomposition: vertical slabs are created at each vertex x-coordinate, the edges inside each slab are sorted by y-position, and a binary search on the slab then a second binary search on the edges pinpoints the region. Notice the step counter — even with many regions the answer is found in a handful of comparisons.

Point location sits in a sweet spot: hard enough to be interesting, easy enough to be fully solved.

• Lower bound: any comparison-based algorithm for point location must use Ω(log n) queries in the worst case. The proof uses a counting argument — there are n + 1 possible answers (one per face), and each comparison at most halves the candidates.
• Kirkpatrick's triangulation hierarchy (1983): David Kirkpatrick showed $O(\log *n*)$ query time with $O(*n*)$ space. He triangulates the subdivision, then repeatedly removes independent sets of low-degree vertices, building a hierarchy of coarser triangulations. A query descends the hierarchy in $O(\log *n*)$ steps.
• Slab decomposition (Dobkin–Lipton, 1976): draw a vertical line through each vertex; inside each slab the edges are non-crossing and can be sorted by y. A query costs $O(\log *n*)$ with $O(*n*^{2})$ storage — simple to implement, expensive in space.
• Persistent search trees (Sarnak–Tarjan, 1986; Edelsbrunner et al., 1986): a plane-sweep builds a balanced BST of edges; making the BST persistent gives $O(\log *n*)$ query time and $O(*n* \log *n*)$ preprocessing in $O(*n* \log *n*)$ space — the practical sweet spot.
• Randomized approaches: randomized incremental triangulation and random trapezoidal maps (Seidel 1991, Mulmuley 1990) reach the same bounds with simpler code.

The outcome: point location is proven optimal — $O(\log *n*)$ per query is both achievable and unavoidable. See also convex hull and closest pair for neighboring gems of computational geometry where the complexity story is equally clean.

Asking "which region contains this point?" is surprisingly universal:

• Geographic information systems (GIS): every "what county is this GPS coordinate in?" query is point location on a political subdivision. Systems like PostGIS and ESRI use optimized slab or R-tree variants for billions of coordinates.
• Game engines: collision detection, zone triggers and area-of-effect spells all reduce to point-in-polygon or point-in-region tests against a prebuilt spatial index.
• Computer graphics: ray tracing and rasterization use point location to decide which triangle of a mesh a ray or pixel falls into. BSP trees are a classic point-location structure for 3-D scenes.
• IP geolocation: mapping an IP address to a country or city uses a numeric interval structure that is a 1-D point location problem, answered in $O(\log *n*)$ with a sorted table.
• Robotics: planning a path in a workspace partitioned into free and obstacle regions requires knowing which region the robot currently occupies.
• Computational cartography: automated label placement, voronoi-based nearest-facility queries and watershed delineation all rely on efficient point location.

Nearly every system that handles spatial data is running point location under the hood — often millions of times per second.

Point location is one of computational geometry's most satisfying chapters: a natural question, a tight lower bound, and multiple algorithms that match it exactly. After preprocessing a map of n edges, every "which region?" query costs only $O(\log *n*)$ comparisons — provably the best possible.

The next time a map app tells you your exact neighborhood in a blink, or a game engine resolves a collision in microseconds, point location is working quietly beneath the surface — turning a potentially slow scan into a logarithmic dive through a prebuilt hierarchy.