Purpose
One circumscribed circle per cell (one circle per cell) is simple but produces exactly as many targets as cells — which fails when a platform caps the number of targets (see target-count constraints). This method replaces the target set with fewer, larger circles while bounding how much extra ground each circle adds. It is a heuristic, explicitly not an optimal set-cover solver.
Source and destination geometry
Source is an h3_cell_set; destination is a list of point_radius circles, one
per selected disk, each carrying the target cells it covers.
Approximation class and boundary behavior
- Exactness
- Approximate — a covered cell means its CENTER lies inside a circle, not that the cell is geometrically contained.
- Coverage guarantee
- Under the defaults (minCoverage = 1, maxOverreach = ∞) every target cell centre is covered and circleCount ≤ cellCount.
- Overreach
- Each circle adds area beyond the cells it covers; the local overreach is bounded by maxOverreach. Report it — this is not exact execution.
- Monotonicity
- A tighter overreach cap never yields fewer circles than a looser one.
Algorithm
Greedy weighted set-cover over candidate disks grown from each cell's centre:
uncovered = all target cells
while uncovered and coverage < minCoverage:
for each seed cell, for k in 0..maxK:
disk = circle at seed centre reaching the k-ring cell centres
covered = target cells whose centre is within the disk radius
localOverreach = (π r² − Σ area(covered)) / Σ area(covered)
skip if localOverreach > maxOverreach
score = |covered ∩ uncovered| / (1 + localOverreach)
pick the highest-scoring disk; remove its covered cells from uncovered
Distances are spherical (haversine) metres; areas come from h3 cellArea — the
same spherical model as the circle methods, so
radii and areas are mutually consistent. The search is O(cells² · maxK); it is
intended for target sets of hundreds to low thousands of cells, not millions.
import { optimizedCircleCover } from "@/lib/h3/optimized-cover";
// Fit a blob of cells under a target cap, accepting up to 1.5x local overreach.
const cover = optimizedCircleCover(cells, { maxOverreach: 1.5, maxK: 3 });
// cover.circles: [{ center: [lat,lng], radiusMeters, coveredCells, localOverreach }]
// cover.circleCount vs cover.cellCount, cover.coverageRatio, cover.uncovered
The tested reference implementation is the TypeScript in lib/h3/optimized-cover.ts.
An equivalent sketch with the Python bindings (h3-py v4) would grow disks from
h3.cell_to_latlng centres and measure with h3.great_circle_distance and
h3.cell_area, applying the same greedy rule.
Conservative vs expansive
- Expansive (higher
maxOverreach): fewer, larger circles; more duplicate eligibility and boundary spill. Pair with an explicit overreach report. - Conservative (lower
maxOverreach, or seed from inscribed circles): more circles, less spill, closer to the target footprint.
Parameters
- maxK
- Neighbourhood radius (grid rings) for disk growth. Default 3.
- maxOverreach
- Reject candidate disks whose local overreach exceeds this. Default ∞.
- minCoverage
- Stop once this fraction of cells is covered. Default 1 (all).
Outputs and quality metrics
Outputs: the circle list plus circleCount, cellCount, coverageRatio, and
uncovered. Compute overreach and duplicate-eligibility
on the returned circles before executing — the reduction in target count is
paid for in overreach, and both numbers must travel with the result.
Known limitations
- Heuristic, not optimal — a smaller admissible cover may exist.
- Coverage is defined on cell centres; a covered cell can still have corner area outside its covering circle. For a hard geometric guarantee, seed radii from circumscribed circles instead.
- Ignores platform minimum radius and radius increments; clamp and re-measure afterwards.
- No antimeridian handling in the greedy step — split trans-antimeridian sets first (see antimeridian handling).