Dobkin-Kirkpatrick Hierarchy

Purpose: A multi-resolution representation of a convex polytope that answers many queries in $O (lo g n)$ — polytope separation, extreme point in a direction, ray shooting, and distance between two convex polytopes.

The Structure

Build a sequence of nested convex polytopes $P = P_{0} \supset P_{1} \supset \dots \supset P_{k}$ , where each $P_{i + 1}$ is obtained from $P_{i}$ by:

finding an independent set of vertices (no two adjacent) with bounded degree — a constant fraction of the vertices, since planar/3-polytope graphs have bounded average degree;
deleting them and re-triangulating the resulting holes.

Each step removes a constant fraction of the vertices, so:

the hierarchy has $O (lo g n)$ levels;
the total size across all levels is $O (n)$ — a geometric series;
the coarsest level $P_{k}$ is a constant-size polytope (a tetrahedron).

How queries use it

Answer the query on the tiny top-level polytope in $O (1)$ , then refine downwards: at each level, the answer on $P_{i + 1}$ is within $O (1)$ combinatorial distance of the answer on $P_{i}$ , because only an independent set of vertices was reinserted. So each level costs $O (1)$ and there are $O (lo g n)$ levels.

$query = O (lo g n) .$

Queries it supports

Query	Time
Is a point inside the polytope?	$O (lo g n)$
Extreme vertex in direction $d$	$O (lo g n)$
Intersection of a line with the polytope (ray shooting)	$O (lo g n)$
Separating plane between two convex polytopes	$O (lo g^{2} n)$
Distance between two convex polytopes	$O (lo g^{2} n)$
Tangent lines/planes from an external point	$O (lo g n)$

The 2D analogue you will actually use

In two dimensions, all of this collapses into something much simpler: a convex polygon’s vertices, in order, form a cyclically unimodal sequence with respect to any linear objective. So:

extreme point in a direction → ternary search or binary search on the hull, $O (lo g n)$ ;
point in convex polygon → binary search on the fan from vertex 0, $O (lo g n)$ ;
tangents from a point → binary search, $O (lo g n)$ ;
line-polygon intersection → two binary searches.

These are 20-line routines and they are what contest problems need. The hierarchy is the machinery required to get the same guarantees in 3D, where “binary search on the boundary” no longer makes sense.

Complexity

Construction: $O (n)$
Space: $O (n)$
Query: $O (lo g n)$ or $O (lo g^{2} n)$

The general technique

Building an $O (lo g n)$ -level hierarchy where each level is a constant-factor coarsening, then refining the answer level by level, is a broadly reusable idea:

Sparse tables and binary lifting — the same doubling in a different dress
Fractional cascading — reuse a binary search across many sorted lists
Borůvka-style contraction — geometric shrinking in graph algorithms
Level-of-detail meshes in graphics — literally this structure

Variants / Use Cases

Convex Hull — build the polytope first
Seidel’s LP — the other route to low-dimensional geometric optimisation
GJK algorithm — the practical collision-detection method for convex bodies; different technique, same problem
3D Geometry — the topic page

whoashish's cp notes

Directory