Module kirkpatrick 

P11.7 — Kirkpatrick hierarchy for guaranteed O(log n) point location in triangulated planar subdivisions. Kirkpatrick hierarchy for O(log n) point location in planar subdivisions (P11.7).

Given a triangulated planar subdivision, the Kirkpatrick hierarchy builds a sequence of progressively coarser triangulations by removing independent sets of low-degree vertices and retriangulating the holes. Point location starts at the coarsest level (a single triangle) and refines downward: at each level, the triangle containing the query is found by checking the (constant-size) set of triangles that replaced it.

Guaranteed O(log n) query time and O(n) space — no randomization.

Reference: Kirkpatrick, “Optimal search in planar subdivisions,” SIAM J. Comput. 1983. Also de Berg et al. §6.3 (simplified variant).

Tier-2 cold construction (uses Vec during build; query is allocation-free).

Structs

KirkpatrickHierarchy

Kirkpatrick point-location hierarchy.

Enums

KirkpatrickError

Error returned by Kirkpatrick hierarchy operations.