Last updated: 2026-09-26

Discrete Voronoi Topic Territories

Legacy engine — documented for historical reference

The live Concept Atlas no longer partitions a fixed grid into non-overlapping Voronoi provinces — territories are now convex hulls around k-blade cluster members, and can genuinely overlap (rendered as swamp terrain) rather than being forced into mutually-exclusive cells. See K-Blades vs. Self-Organizing Maps: How the Live Concept Atlas Works Now for the current approach. This page remains as a record of the grid-based approach the site used previously.

Spatial Partitioning & Political Geography

This article explains how the Concept Atlas partitions its $40 \times 40$ grid into discrete, non-overlapping topic provinces using spatial Voronoi nearest-category assignment, and how contested border lines are rendered along shared hex sides.

The Challenge of Overlapping Territories FoundationalKnowledge that endures for decades — core principles

In early iterations of spatial concept maps, topic regions were rendered as overlapping translucent rectangles or ellipses. While simple to compute, overlapping shapes created visual clutter, blurred domain boundaries, and made it difficult for readers to discern which category governed a particular region of the map.

To create an intuitive map resembling a political atlas of countries, the grid is partitioned into discrete, mutually exclusive Voronoi provinces — a nearest-centroid space partition named after Georgy Voronoi, whose 1908 work on quadratic forms formalised the construction, and now a standard tool of computational geometry [1]. The everyday intuition is the same one used to draw postcode-style catchment maps: every point on the plane belongs to whichever seed (here, a topic centroid) it is closest to, and the boundary between two neighbouring regions is always the perpendicular bisector between their seeds. Applied to a fixed hex grid rather than a continuous plane, that same rule is what produces the discrete province structure below.1-nearest-neighbour classifiers draw these cells

The trade-off this legacy engine accepted was the one built into the nearest-centroid rule itself: every grid cell gets exactly one owner, however close the runner-up category's centroid actually was. A page sitting almost equidistant between two topics — borderline — still had to be coloured as belonging wholly to one province or the other, with no way to show that it was nearly as much the other. That is the specific limitation the current k-blade engine (linked above) was built to remove, by letting a page's territory membership be a real, renderable overlap rather than a forced single choice.cf. overlapping membership and its affinity margin

Spatial Voronoi Category Assignment FoundationalKnowledge that endures for decades — core principles

During atlas generation in som_atlas.py, every grid cell $(x, y)$ on the $40 \times 40$ map is evaluated for category affinity:

The centroid $(\bar{x}_c, \bar{y}_c)$ of every topic category $c \in C$ is computed from the locations of its constituent document nodes.
Each hex cell $(x, y)$ calculates its Euclidean distance $d((x,y), (\bar{x}_c, \bar{y}_c))$ to all category centroids.
The cell is assigned to the nearest category $c^* = \min_{c} d((x,y), (\bar{x}_c, \bar{y}_c))$, generating a 2D matrix of category labels (grid_categories).

Rendering Contended Territory Borders Applied / MethodologicalKnowledge with a 5–10 year half-life — stable practice

To visualise the borders separating neighbouring country provinces, the SVG renderer inspects every hex cell $(x, y)$ and its adjacent neighbours $(nx, ny)$. When two neighbouring cells belong to different categories ($c_{(x,y)} \neq c_{(nx,ny)}$), a dashed border line (<line class="atlas-territory-border">) is drawn along the shared hexagon side:

\[E_1 = M + \vec{u} \cdot \frac{L}{2}, \quad E_2 = M - \vec{u} \cdot \frac{L}{2}\]

Where $M$ is the midpoint between hex centres, $\vec{u}$ is the perpendicular unit vector along the shared edge, and $L = \frac{R}{\sqrt{3}}$ is the exact side length of the hexagon. This ensures border lines lie 100% flush along hexagon edges with zero orthogonal spikes or whiskers.

Interactive Territory Hover & Inspection Ephemeral / ToolingKnowledge that evolves in months to a year — check for updates

Hovering over any regional header text (e.g. ✦ SOFTWARE ENGINEERING ✦) or any hex tile within category $C$ activates territory inspection mode:

All hex tiles and border lines belonging to category $C$ highlight with the is-territory-hovered CSS class, displaying a subtle gold or crimson parchment glow.
The fixed 3-line inspection banner displays the territory domain title, province status, and navigation guidance.

Concept Mapping and Self-Organizing Maps — the SOM pipeline this Voronoi partition was built directly on top of, using the same trained grid's topic centroids.
K-Blades vs. Self-Organizing Maps: How the Live Concept Atlas Works Now — the current replacement, using real convex hulls that can overlap instead of forcing every cell into exactly one province.
Graph Traversal & Pathway Interrogation — the road network that follows this same grid's low U-Matrix valleys, threading between the territory borders described here.

References

F. Aurenhammer, "Voronoi Diagrams — A Survey of a Fundamental Geometric Data Structure," ACM Computing Surveys, vol. 23, no. 3, pp. 345–405, 1991. https://doi.org/10.1145/116873.116880