Weighted Voronoi Diagram¶
A spatial partition whose cells assign each point to the site minimizing a declared weighted distance or power score.
Core Idea¶
A weighted Voronoi diagram divides a geometric domain into cells according to which weighted site scores best at each point. State the scoring formula before interpreting the picture: different formulas need not produce the same cells or boundaries. In an additively weighted Apollonius diagram, the score is Euclidean distance to a site minus its weight. In a power diagram, it is squared Euclidean distance minus its weight. The site or sites with the least score own each point.[ref-ff7cd365848c][ref-1c90beaaa50c]
Scope of Application¶
The directly verified cases are planar computational-geometry constructions using weighted disks or weighted points. A real-world “influence” map becomes a literal instance only when its positions, weights, distance or power rule, and cell assignment are specified. Some input sites may own no cell at all.[ref-ff7cd365848c][ref-1c90beaaa50c]
Clarity¶
Ask what the weights mean, which formula is used, and how a tie is treated. Equal-score points form a boundary only if the tied sites also have the lowest score; another site may beat both. A tie convention can assign boundary points uniquely when an application needs disjoint cells.[ref-ff7cd365848c][ref-1c90beaaa50c]
Manages Complexity¶
The diagram summarizes continuous point-to-site comparisons as regions with stable winning sites. That summary depends on the chosen formula. A site hidden by stronger competitors can disappear from the visible cells even though it remains in the input.[ref-ff7cd365848c][ref-1c90beaaa50c]
Abstract Reasoning¶
To inspect a proposed boundary, compare the two sites' scores and then check that no third site scores lower. Changing from additive distance to power distance requires recomputing the cells. Under the power formula, pairwise equal-power separators are affine; curved boundaries are not universal to weighted diagrams.[ref-ff7cd365848c][ref-1c90beaaa50c]
Knowledge Transfer¶
The site, weight, score, minimum, and cell roles transfer between additive and power variants. Their numerical weights, boundary geometry, and associated data structures do not transfer unchanged. The broader act of comparing values under one frame belongs to the Comparison Prime; spatial cells and distance-based rules keep this entry domain-specific.
Example¶
CGAL's Apollonius construction scores a point by its distance to each disk center minus that disk's weight. Its power-diagram construction instead uses squared distance to a weighted point minus the point's weight; the resulting diagram is dual to a regular triangulation. Both compare sites under one declared rule and assign cells to minimum scorers, but they need not yield the same boundaries.[ref-ff7cd365848c][ref-1c90beaaa50c]
Relationships to Other Abstractions¶
Current abstraction Weighted Voronoi Diagram Domain-specific
Parents (1) — more general patterns this builds on
-
Weighted Voronoi Diagram is part of Comparison Prime
Every weighted Voronoi cell requires comparing site scores under one declared rule at each point; Comparison is an internal constituent of the diagram.
Hierarchy path (1) — routes to 1 parentless root
- Weighted Voronoi Diagram → Comparison
Neighborhood in Abstraction Space¶
Weighted Voronoi Diagram sits in a sparse region of the domain-specific corpus (96th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2721 abstractions)
Nearest neighbors
- Gower's Distance — 0.78
- Mass Point Geometry — 0.77
- Monotonic Query — 0.77
- Roman Dominating Set — 0.76
- Monotonic Function — 0.76
Computed from structural-signature embeddings · 2026-10-17
Not to Be Confused With¶
A power diagram is one weighted Voronoi variant, not the entire family.[^ref-1c90beaaa50c] An unweighted diagram is a limiting case, not evidence that the weights affected any cell.[ref-ff7cd365848c][ref-1c90beaaa50c] A partition with disjoint blocks requires an explicit tie convention at boundaries; without one, the catalog's Partition Prime is not a strict parent.
References¶
[^ref-ff7cd365848c]: CGAL, 2D Apollonius Graphs User Manual (CGAL 6.2.1), “Definitions,” by Menelaos Karavelas and Mariette Yvinec. Official full technical documentation, directly inspected for additive score, cells, disk interpretation, and hidden sites. The /latest/ page displayed version 6.2.1 when inspected; it may later advance.
[^ref-1c90beaaa50c]: CGAL, Regular_triangulation_2 Class Reference (CGAL 6.2.1), “Definition.” Official full technical documentation, directly inspected for weighted points, power product, minimum-power cells, and regular-triangulation dual. The /latest/ page displayed version 6.2.1 when inspected; it may later advance. Franz Aurenhammer's 1987 original paper abstract independently confirms the power-diagram formal object; no full-text claims are attributed to that abstract.