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 assigns each point in a geometric domain to a site that minimizes a declared score combining distance and that site's weight. The resulting cells tell us which site wins the comparison at each point. The score formula is part of the identity of a particular variant: additively weighted diagrams and power diagrams share the site/weight/minimum/cell structure but are different geometric constructions.[1][2]
For an additively weighted Apollonius diagram, a site with center \(c_i\) and weight \(w_i\) is scored by \(\lVert x-c_i\rVert-w_i\). For a power diagram, a weighted point \((p_i,w_i)\) is scored at \(x\) by \(\lVert x-p_i\rVert^2-w_i\). Both assign points by the minimum, but their cell boundaries and dual structures need not match. A weight cannot be interpreted without its chosen formula and units.[1][2]
Structural Signature¶
- A geometric domain and competing sites. The same query point must be compared with a finite set of positioned sites. With no shared domain or competition, there is no Voronoi assignment.[1][2]
- Per-site weights. Each site carries a parameter that changes its score relative to other sites. Equal or zero weights provide an unweighted limiting case, but the weighted construction must state the convention.[1][2]
- A fixed weighted score rule. The formula maps a query point and a weighted site to a comparable value. Additive Euclidean distance and squared-distance power are different rules; swapping them changes the diagram.[1][2]
- Minimum-score assignment. A cell collects points where its site's score is no greater than competitors' scores. A tie between co-minimal scores marks a cell boundary; a two-site equality hidden by a third, lower score does not. A tie convention is needed when an application requires a single winner.[1][2]
- Induced cells. The assignment makes a spatial subdivision. Some input sites can have empty cells and therefore never win at any query point; nonempty ownership is not guaranteed.[1][2]
These roles define a formal family. Variant-specific geometry belongs to the selected score rule rather than to an assumed universal shape of weighted Voronoi cells.
What It Is Not¶
It is not one fixed formula under several names. The Apollonius score subtracts a weight from Euclidean distance; power distance subtracts a weight from squared Euclidean distance. Numerical weights from one rule cannot simply be transferred to the other. The power diagram's dual is a regular triangulation, a fact that must not be assigned automatically to an additive diagram.[1][2]
It is not a claim that every site owns a nonempty region. Both cited constructions allow hidden sites. Nor is every boundary curved: equating the power scores of two sites cancels the common \(\lVert x\rVert^2\) term, leaving an affine equal-power line in the plane. The frozen seed's curved-boundary language therefore cannot define the family.[1][2]
Scope of Application¶
The directly supported scope is planar computational geometry with weighted sites. CGAL documents an additively weighted diagram of disk-like sites and a power diagram of weighted points, with regular triangulation as the latter's dual. The shared abstraction can guide comparisons between these constructions, but an actual diagram must choose one score formula, domain, and tie treatment.[1][2]
Applications to influence, service regions, or competitive territories require extra modeling evidence: a physical or social “strength” cannot be silently substituted for \(w_i\). Here the source-grounded examples are formal geometric constructions, not claims about a particular real-world allocation.
Clarity¶
When reading or constructing a weighted Voronoi diagram, write the score \(s_i(x)\) before drawing cells. State what \(w_i\) means, which direction of score is preferred, and what happens at equality. Then test whether each input site actually has a winning region. A bare picture of unequal regions does not identify which weighted rule produced it.[1][2]
For example, the phrase “the larger site wins more space” is too loose. In the additive convention, a positive increase in \(w_i\) lowers that site's score; in the power convention, increasing the scalar weight also lowers its score, but in squared-distance units. Those statements are formula-specific and do not imply that all weighted constructions share one boundary shape.[1][2]
Manages Complexity¶
The diagram turns a continuous family of point-to-site comparisons into cells with a stable winning site. Instead of separately comparing every site at every point when reasoning about a region, an analyst can use the cell structure and its boundaries. The compression is valid only after a score rule is fixed; a generic weighted-Voronoi label without a rule does not determine the cells.[1][2]
Hidden sites also simplify the output while complicating interpretation. A site present in the input can disappear from the visible cell diagram because another site wins everywhere. CGAL's Apollonius and regular-triangulation documentation both distinguish input sites from sites represented by nonempty cells.[1][2]
Abstract Reasoning¶
The basic test is pairwise equality and inequality. For two sites, solve \(s_i(x)=s_j(x)\) for a potential boundary and compare scores on either side; then compare the winning score with all other sites. This distinguishes a true cell edge from a two-site tie hidden by a third site.[1][2]
Changing the score rule is a meaningful counterfactual. Under power distance, the common squared-coordinate term cancels from pairwise equality, so the separator is affine. Under additive Euclidean distance, that cancellation does not occur in the same way. Therefore one should recompute boundaries after moving from an Apollonius diagram to a power diagram rather than treating them as cosmetic alternatives.[1][2]
Knowledge Transfer¶
The transferable method within geometry is to identify sites and weights, compute a score for each site at each point, and take the least score to form cells. That procedure survives the shift from weighted disks to weighted points. The numerical formula, geometric interpretation of weight, boundary geometry, and appropriate dual data structure do not transfer unchanged.[1][2]
Calling any social or economic territory map a “weighted Voronoi diagram” is an analogy until a defensible site, weight, distance function, and assignment rule have been specified. The domain-specific cargo is a mathematical spatial partition, not the general idea that stronger competitors may influence larger areas.
Examples¶
Canonical: additively weighted Apollonius diagram¶
CGAL defines sites \(P_i=(c_i,w_i)\) and scores a point \(x\) by \(\delta(x,P_i)=\lVert x-c_i\rVert-w_i\). The cell for a site consists of points for which that score is minimal among sites; a site may be hidden with no cell. Mapped back: the plane is the domain, centers are sites, \(w_i\) are per-site additive weights, \(\delta\) is the declared score, minimum comparison determines cells, and equal-score loci give candidate boundaries. A disk-radius reading is available for nonnegative weights, but it is not the definition of every weighted diagram.[1]
Applied formal construction: power diagram¶
CGAL's regular-triangulation documentation treats weighted points \((p_i,w_i)\) as sites. For a query point \(x\), power is \(\lVert x-p_i\rVert^2-w_i\); the least-power site owns the cell, and the diagram is dual to a regular triangulation. Mapped back: the plane and weighted points supply the domain and sites, the power formula supplies the score, minimum comparison supplies cells, and equal powers supply affine candidate separators where the tied sites also have the least score. A weighted point may be hidden, so the regular triangulation can use only a subset of input centers.[2]
Structural Tensions¶
The two constructions exhibit different formulas and geometric consequences, but the inspected sources do not establish a universal optimization trade-off between them. Choosing additive distance or power distance changes the modeled relation itself. This section therefore records no invented two-sided tension; an application would need its own objective and evidence before comparing the alternatives.[1][2]
Structural–Framed Character¶
The entry is mostly structural within geometry. Vocabulary travel: “nearest” and “weight” are broad words, but the literal test requires a spatial domain and declared score. Evaluative weight: a cell identifies a minimum under a model, not an objectively best site outside it. Institutional origin: software libraries expose the constructions, but their mathematical definitions do not depend on the library. Human-practice dependence: the analyst chooses formula and weights; once chosen, cells follow from comparison. Import versus recognition: additive and power diagrams are literal variants; assigning a similar map to a social process without a score rule is analogy. Its character: mixed-structural, because the minimum-score/cell relation transfers between unlike geometric formulas while positions, distance, and spatial cells keep literal instances inside geometry.
Structural Core vs. Domain Accent¶
The liftable skeleton is choosing a winner by minimizing a weighted score. The catalog’s Comparison Prime owns that broader shared-frame evaluation pattern; no new Prime is asserted from this portable skeleton. The domain core adds positions in geometric space, distance- or power-based score functions, and cells made of points with the same winner. Remove those ingredients and the result may be a ranking or classification, but it is no longer a weighted Voronoi diagram. This is why the entry remains domain-specific despite its broadly reusable minimum-selection idea.
Instantiates / Related Primes¶
This entry is part of Comparison.
The catalog's Comparison Prime names the shared-frame score operation that every cell assignment requires. It is an identity-bearing part of this diagram, giving a strict composition edge. Partition names an exhaustive division into nonoverlapping blocks; a weighted Voronoi diagram yields that form only after a tie convention assigns boundary points uniquely, so Partition is not a strict parent. A power diagram and an Apollonius diagram are the closest formal variants, not aliases for one formula.[1][2]
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.At each query point, positioned sites are comparands, the fixed weighted score is the shared frame, and the minimum or co-minimum relation determines cell membership and boundaries. Without this comparison there are weighted sites but no winning cells. Comparison also occurs without geometry or weighted cells, so it is an identity-bearing constituent rather than a synonym for the diagram. The parent is inside the child.
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¶
- Unweighted Voronoi diagram. Equal weights can recover it as a limiting case, but weighting must affect score comparisons to matter.[1][2]
- Power diagram alone. It is one weighted variant with squared-distance power, not the whole family.[2]
- Every site having a region. A sufficiently dominated site can be hidden and have an empty cell.[1][2]
- A universal curved-boundary claim. Power bisectors are affine under the documented formula.[2]
References¶
[1] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v
[2] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x