How to Learn Kirkpatrick’s Planar Point-Location Algorithm: Triangulations, Low-Degree Independent Sets, Hierarchies and O(log n) Queries

How can a map with thousands of polygonal regions answer “which region contains this point?” in logarithmic time? Kirkpatrick’s point-location structure solves the problem by repeatedly simplifying a triangulated planar subdivision. The query does not search every triangle; it descends through a small hierarchy of progressively finer triangulations.

David Kirkpatrick’s 1983 algorithm is a classic example of a static geometric data structure with optimal asymptotic bounds: O(n) storage and O(log n) query time. This Learning Hall article builds from orientation tests and triangulation through low-degree independent sets, vertex removal, overlap links, construction complexity, robust predicates and professional implementation choices.

Quick Read

Point location asks which face of a planar subdivision contains a query point.
Kirkpatrick first works with a triangulated subdivision enclosed by a large outer triangle.
At each level, choose an independent set of low-degree interior vertices.
Remove those vertices and retriangulate the holes they leave.
Because the removed vertices have bounded degree, each new triangle overlaps only a constant number of triangles from the finer level.
A constant fraction of vertices can be removed per level, so the hierarchy has O(log n) levels.
The top level contains only a constant number of triangles.
A query starts at the top and follows overlap links downward, testing only O(1) candidate triangles per level.
Query time is O(log n); total hierarchy size is O(n).
Robust orientation predicates and boundary conventions matter as much as asymptotic analysis in production geometry.

1. Beginner Level: What Is Point Location?

A planar subdivision partitions the plane into regions using noncrossing edges. Think of a map, a CAD drawing, a navigation mesh or a planar graph embedding. Given query point q, point location returns the face containing q.

Without preprocessing, we might test q against every polygon or triangle, which can cost O(n) per query. Static point-location structures spend time once so later queries are much faster.

2. Reduce the Geometry to Triangles

Triangles are ideal because membership can be tested with a constant number of orientation predicates. Kirkpatrick’s hierarchy therefore assumes a triangulation of the subdivision. If original faces are polygons, triangulate each face without crossing subdivision edges.

Then surround the entire subdivision with a large outer triangle and triangulate the annular area between the original boundary and that triangle. The outer triangle remains fixed throughout simplification and gives the hierarchy one simple root region.

3. Point-in-Triangle by Orientation

For counter-clockwise triangle (a,b,c), q lies inside or on the boundary when it is consistently on the same side of each directed edge:

orient(a,b,q) ≥ 0
orient(b,c,q) ≥ 0
orient(c,a,q) ≥ 0

where:

orient(a,b,q)
= (b.x-a.x)(q.y-a.y) - (b.y-a.y)(q.x-a.x)

In exact mathematics this is simple. In floating-point software, nearly collinear inputs can flip sign because of rounding, so robust predicates deserve explicit design attention.

4. The Strange Move: Delete Vertices

Kirkpatrick does not build a search tree by sorting triangles. Instead, it creates a sequence of simpler triangulations:

T0 = original fine triangulation
T1 = coarser triangulation
T2 = still coarser
...
Tk = constant-size triangulation

Each coarser level is obtained by removing selected vertices from the finer level and retriangulating the polygonal holes.

5. Why Low-Degree Vertices?

Removing a vertex of degree d leaves a polygonal hole with d boundary vertices. If d is bounded by a constant, retriangulating that hole creates only O(1) new triangles.

Planar triangulations have low average degree. Therefore many vertices have degree bounded by a small constant. Kirkpatrick’s construction selects a large set of low-degree vertices, often presented with a threshold such as degree at most 8.

6. Why the Removed Set Must Be Independent

Do not remove adjacent selected vertices simultaneously. If two removed vertices share an edge, their holes interact and the local-overlap argument becomes messy. Choose an independent set: no two selected vertices are adjacent.

Because low-degree vertices are plentiful and each selected vertex excludes only a constant-size neighbourhood, a greedy process can choose an independent set containing a constant fraction of all remaining vertices.

7. Constant-Fraction Shrinkage Creates O(log n) Levels

Suppose each simplification removes at least αn vertices for some constant α>0. Then the next level has at most (1−α)n vertices. Repeating gives geometric decay:

n,
(1-α)n,
(1-α)²n,
...

After O(log n) levels only a constant number remain. This is the first half of the query bound.

8. Build Overlap Links Between Levels

When a hole is retriangulated, a new coarse triangle covers a region that was previously covered by several finer triangles. Store links between every coarse triangle and the finer triangles it overlaps.

Because each removed vertex had bounded degree and selected vertices were independent, one coarse triangle overlaps only O(1) finer triangles. That bounded fan-out is the second half of the O(log n) query proof.

9. The Hierarchy Is a DAG, Not Necessarily a Tree

A finer triangle can overlap more than one coarser triangle along boundaries, and a coarser triangle can link to several finer triangles. The natural structure is therefore a directed acyclic graph from coarse levels toward fine levels.

For a query, however, we maintain only the small candidate set compatible with the current containing triangle. The DAG gives the search path without forcing a strict parent-child partition.

10. Query From Coarse to Fine

LOCATE(q):
    t = top-level triangle containing q

    for level from coarse to fine:
        for each finer triangle child of t:
            if q lies in child:
                t = child
                break

    return original face label attached to t

There are O(log n) levels and only O(1) children to test at each level, so each query takes O(log n) orientation work.

11. Why Total Storage Is O(n)

The number of vertices and triangles falls geometrically. Summing all levels gives:

n + cn + c²n + ... = O(n),  for 0 < c < 1

Because each triangle stores only constant overlap information, total hierarchy storage is linear.

12. Construction Complexity

Kirkpatrick’s original result achieves linear-time hierarchy construction under the subdivision representation and triangulation assumptions used in the paper. In a full software pipeline, initial polygon triangulation and topology validation may carry their own costs. Keep the complexity of building the Kirkpatrick hierarchy separate from the complexity of importing arbitrary geometry.

13. Worked Example: One Removed Vertex

Suppose interior vertex v has degree 5. Its five incident triangles form a pentagonal star-shaped neighbourhood. Removing v leaves a five-vertex polygonal hole. Retriangulating the pentagon creates three coarse triangles.

Each of those three new triangles overlaps only triangles formerly incident to v. Since degree 5 is constant, the number of overlap links is constant. That local picture is the entire global method repeated at scale.

14. Boundary Queries Need a Contract

What if q lies exactly on an edge or vertex? Mathematically it belongs to more than one closed face. Production software must define a policy:

return any incident face;
return a boundary object rather than a face;
use half-open ownership rules;
return all incident faces.

The data structure cannot compensate for an undefined API contract.

15. Numerical Robustness

Fast point location depends on reliable point-in-triangle decisions. With floating coordinates, robust orientation predicates such as adaptive exact arithmetic are often more important than shaving a few comparisons.

Never add a global epsilon to every orientation test without understanding scale. A tolerance that works for metre-scale coordinates may be meaningless for nanometres or astronomical coordinates.

16. Data Structures for the Triangulation

A half-edge or DCEL representation is natural because simplification needs adjacency, cyclic incident-edge order and face updates. Each hierarchy level can store immutable triangles plus overlap links once constructed.

The original paper emphasises compatibility with practical subdivision representations. The professional challenge is usually preserving topology during repeated deletion/retriangulation, not point-in-triangle arithmetic.

17. Kirkpatrick vs Trapezoidal Maps

Randomized incremental trapezoidal-map point location is another famous O(log n)-expected-query approach and is common in computational-geometry teaching. Kirkpatrick gives deterministic worst-case logarithmic query time with a conceptually different hierarchy.

The choice is not only asymptotic: dynamic updates, implementation complexity, degeneracies and library ecosystem all matter.

18. Failure Modes

Removing adjacent vertices in the same level. Local holes can interfere.
Removing high-degree vertices without controlling overlap. Fan-out may cease to be constant.
Failing to retriangulate holes without crossings. The hierarchy must remain a valid planar subdivision.
Losing original face labels during triangulation. Final triangles must map back to source faces.
Assuming a hierarchy node has only one child. Overlap structure is a DAG.
Using nonrobust orientation tests near boundaries.
Forgetting outer-triangle handling for points outside the original domain.

19. Professional Testing Strategy

Compare queries against brute-force face testing on small subdivisions.
Generate random triangulations and thousands of random query points.
Test points near every edge and vertex using exact or high-precision reference predicates.
Verify every simplification level remains planar and triangulated.
Assert selected removal sets are independent and degree-bounded.
Measure vertices per level to confirm geometric shrinkage.
Assert every fine triangle is covered by at least one appropriate coarser overlap link.
Test points outside the original subdivision but inside/outside the enclosing triangle according to the API contract.

20. How to Learn It Efficiently

Start with a hand-drawn triangulation of 10–15 vertices. Circle low-degree vertices, then choose a nonadjacent subset. Remove one vertex and retriangulate its hole with pencil. Next draw arrows from each new triangle to the old triangles it overlaps. Once learners see two hierarchy levels, the query procedure becomes almost obvious.

Use the subgoals triangulate → choose removable set → simplify → link overlap → descend query. Worked examples and faded/Parsons-style activities are well suited to this algorithm because the conceptual difficulty is decomposition into stages rather than syntax.

21. Professional Applications

Static map and GIS region queries.
CAD and planar arrangement lookup.
Navigation meshes.
Planar graph embeddings and mesh processing.
Preprocessed geometric search in simulation.
Teaching hierarchical geometric data structures and optimal query bounds.

22. Practice Problems

Triangulate a polygonal subdivision and attach original face labels.
Find a low-degree independent set in a given triangulation.
Remove one selected vertex, retriangulate the hole and list overlap edges.
Prove geometric shrinkage implies O(log n) levels.
Prove the sum of all hierarchy sizes is O(n).
Implement robust point-in-triangle testing with an orientation primitive.
Compare query speed against brute-force triangle scanning.
Design explicit semantics for points exactly on subdivision boundaries.

23. Sources and Further Reading

Final idea: Kirkpatrick makes search fast by making the world temporarily simpler. Each level removes enough detail to shrink the problem, but stores just enough overlap information to recover that detail during a query. The logarithmic search bound is the product of two disciplined choices: constant-fraction simplification and constant-fan-out refinement.

Small Group Tutorials