Power Diagrams: Exploration on Weighted Voronoi

Authors

Batsambuu Batbold

Christopher Enberg

Blake Kell

Published

November 13, 2025

Introduction

This project explores a different version of a Voronoi Diagram: what happens when the sites are not all treated equally?

In many real-world scenarios, locations have different levels of “size” or “power.” A large hospital serves a wider area than a small clinic, or a hypermarket offers a wider range of options than a small grocery store. To model this, our project explores Weighted Voronoi Diagrams, which give weight to the sites according to their importance.

We mostly use Euclidean distance when constructing a Voronoi Diagram, which assumes the weights of the sites are equal. To move beyond this, we must give away Euclidean distance and consider another type of distance measurement that takes the different weights of the sites into account. Out of such variations, we will focus on the Power Diagram, which is based on the Power of a point.

Power Diagrams

1. The Power of a Point

The power of a point $P$ with respect to a circle $\omega$ with center $O$ and radius $r$ is defined as:

\[ \text{Pow}_\omega(P) = OP^2 - r^2 \] Thus, if we think of the sites as centers of circles and the weights as their radii, then we can use the power of a point as our “distance” between the point and the site.

Here, notice that $OP^2$ is the squared Euclidean distance between the site and a point. A bigger radius (weight) reduces this “distance” by subtracting a larger value, which gives the site more range. For example (Figure $1$), if we have two sites with different weights and a point at an equal Euclidean distance from each site, the point will belong to the site with a larger radius (the larger weight).

$\text{Figure } 1$: Point $P$ is at an equal Euclidean distance $d$ from both sites $O_1$ and $O_2$. Because the radius (weight) $r_2$ is greater than $r_1$, $P$’s “power distance” to $O_2$ is smaller, and it belongs to the red site’s region.

2. The Radical Axis

In a standard Voronoi diagram, the Voronoi edges are the perpendicular bisector between two sites because that’s where Euclidean distances are equal. Similarly, we define the edges of a Power Diagram as the set of points where the power is equal for two circles:

\[ \text{Pow}_{\omega_1}(P) = \text{Pow}_{\omega_2}(P) \] This set of points is called the Radical Axis of the circles. The following two theorems about the Radical Axis demonstrate why this is such a robust choice.

Radical Axis Theorem

Let $\omega_1$ and $\omega_2$ be circles with distinct centers $O_1$ and $O_2$. The radical axis of $\omega_1$ and $\omega_2$ is a straight line perpendicular to $O_1O_2$.

$\text{Figure } 2$: The radical axis (green line) represents the set of points with equal power to $\omega_1$ and $\omega_2$. As the theorem states, this axis is a straight line and is perpendicular to the line of centers $O_1O_2$ (gray dashed line).

Click to see Proof

Let $P = (x, y)$ be any point on the radical axis. Let the centers be $O_1 = (x_1, y_1)$ and $O_2 = (x_2, y_2)$, with radii $r_1$ and $r_2$.

By the definition of the radical axis, the power is equal for both circles: \[ \begin{align} \text{Pow}_{\omega_1}(P) &= \text{Pow}_{\omega_2}(P) \\ \Rightarrow (x - x_1)^2 + (y - y_1)^2 - r_1^2 &= (x - x_2)^2 + (y - y_2)^2 - r_2^2 \end{align} \]

After expanding the squared terms: \[(x^2 - 2xx_1 + x_1^2) + (y^2 - 2yy_1 + y_1^2) - r_1^2 = (x^2 - 2xx_2 + x_2^2) + (y^2 - 2yy_2 + y_2^2) - r_2^2\]

Notice that the $x^2$ and $y^2$ terms on both sides cancel out, leaving a linear equation. \[ \begin{align} - 2xx_1 + x_1^2 - 2yy_1 + y_1^2 - r_1^2 = - 2xx_2 + x_2^2 - 2yy_2 + y_2^2 - r_2^2 \\ \Rightarrow 2(x_2 - x_1)x + 2(y_2 - y_1)y + (x_1^2 + y_1^2 - r_1^2 - x_2^2 - y_2^2 + r_2^2) = 0 \end{align} \]

Since $O_1$ and $O_2$ are distinct, at least one of $(x_2 - x_1)$ or $(y_2 - y_1)$ is non-zero. Thus, the above equation is one of a straight line.

Furthermore, the slope of this line is: \[m_{\text{axis}} = \frac{-2(x_2 - x_1)}{2(y_2 - y_1)} = -\frac{x_2 - x_1}{y_2 - y_1}\]

The slope of the line of centers $O_1O_2$ is: \[m_{\text{centers}} = \frac{y_2 - y_1}{x_2 - x_1}\]

It follows that the product of the slopes is $m_{\text{axis}} \times m_{\text{centers}} = -1$. Therefore, the radical axis is perpendicular to the line of centers. $\blacksquare$

This means that, just like a perpendicular bisector, the radical axis also divides the plane into two half-planes.

Radical Axis Concurrence Theorem

The three pairwise radical axes of three circles concur at a point, called the Radical Center.

$\text{Figure } 3$: The three pairwise radical axes (green, orange, and purple lines) of the circles $\omega_1$, $\omega_2$, and $\omega_3$ are all concurrent (intersect) at a single point, which we call the **Radical Center**.

Click to see Proof

Let the three circles be $\omega_1$, $\omega_2$, and $\omega_3$.

Let $L_{12}$ be the radical axis of $\omega_1$ and $\omega_2$. By definition, for any point $P \in L_{12}$, we have: \[\text{Pow}_{\omega_1}(P) = \text{Pow}_{\omega_2}(P)\]

Let $L_{23}$ be the radical axis of $\omega_2$ and $\omega_3$. For any point $P \in L_{23}$: \[\text{Pow}_{\omega_2}(P) = \text{Pow}_{\omega_3}(P)\]

Now, consider the point $P_{\text{center}}$ where $L_{12}$ and $L_{23}$ intersect. (We can assume the general position where they are not parallel).

Since $P_{\text{center}} \in L_{12}$, we know: \[\text{Pow}_{\omega_1}(P_{\text{center}}) = \text{Pow}_{\omega_2}(P_{\text{center}})\]

Since $P_{\text{center}} \in L_{23}$, we also know: \[\text{Pow}_{\omega_2}(P_{\text{center}}) = \text{Pow}_{\omega_3}(P_{\text{center}})\]

By the transitive property, it follows that: \[\text{Pow}_{\omega_1}(P_{\text{center}}) = \text{Pow}_{\omega_3}(P_{\text{center}})\]

Therefore, the intersection point $P_{\text{center}}$ must also be on the third radical axis, $L_{13}$, which follow that all three lines pass through the same point. $\blacksquare$

Again, this theorem gives us the position of the Voronoi vertices. Ultimately, these two theorems suggest that the resulting power diagram will have a similar regional structure to a regular Voronoi diagram.

3. The Power Diagram

More formally, we define the Power region $\text{Pow}(s)$ of a site $s \in S$ with a weight of $r_s$ as:

\[ \begin{align*} \text{Pow}(s) = \{x \in \mathbb{R}^2 \ | \ \text{Pow}_{\omega_s}(x) \le \text{Pow}_{\omega_q}(x) \text{ for all } q \in S \}, \\ \text{ where } \omega_i \text{ is the circle centered at } i \text{ with radius of } r_i \end{align*} \]

Thus, the Power diagram is a collection of these regions. To explore the properties of the power diagram, we generate the Power Diagrams for a set of sites.

Algorithm

Below is the main idea of the algorithm for constructing a power diagram:

FUNCTION weighted_delaunay(input_points):

    # 1. Initialization
    # Create a bounding triangle that is guaranteed to contain all input points.
    super_triangle = CREATE_SUPER_TRIANGLE(input_points)
    
    # The triangulation starts with just this single, large triangle.
    triangulation = [super_triangle]

    # 2. Incremental Insertion Loop
    # Process each site one by one, adding it to the triangulation.
    FOR EACH point IN input_points:

        bad_triangles = [] # Triangles whose power circle contains the point
        
        # a. Find all "bad" triangles
        FOR EACH triangle IN triangulation:
            IF point IS INSIDE triangle.power_circle():
                ADD triangle TO bad_triangles
        
        # b. Find the boundary of the polygonal cavity
        boundary_edges = []
        FOR EACH triangle IN bad_triangles:
            FOR EACH edge OF triangle:
                IF edge IS NOT SHARED by any other triangle in bad_triangles:
                    ADD edge TO boundary_edges

        # c. Remove bad triangles and re-triangulate the cavity
        REMOVE all triangles in bad_triangles FROM triangulation
        
        FOR EACH edge IN boundary_edges:
            new_triangle = CREATE_TRIANGLE(edge.vertex1, edge.vertex2, point)
            ADD new_triangle TO triangulation

    # 3. Cleanup
    # Remove any triangles from the final list that are connected to the
    # vertices of the initial super-triangle.
    final_triangulation = []
    FOR EACH triangle IN triangulation:
        IF triangle DOES NOT SHARE vertices with super_triangle:
            ADD triangle TO final_triangulation

    # 4. Return the result
    RETURN final_triangulation

The full Python implementation, including the unweighted Voronoi diagram and the code generating the figures below, is available in the GitHub repository linked at the bottom of this page.

Visual Demonstration

$\text{Figure } 4$: Comparison between unweighted and weighted Voronoi diagrams

Observation

From the figures above, we can see one of the main differences between Standard Voronoi Diagrams and Weighted Voronoi diagrams: Voronoi regions no longer require a site from $S$ to be located inside each one.

Depending on the weights of nearby sites and hoe close they are to one another, Voronoi regions within the Power Diagram can possibly contain either no or multiple sites of $S$.

If we consider weights as some sort of popularity or overall size, this phenomenon starts to make more sense - If you’re in range of a site that can accommodate more of your needs, you’re more likely to go to that site even if there are smaller ones closer to you.

Conclusion

Summary

In this project, we have discussed what it means to create a Power diagram, and how their construction is equivalent to a Voronoi diagram. We adapted a standard Voronoi region algorithm to utilize this new measure, and analyzed how the two diagrams differ from one other.

This allows us to better understand how we can adapt Voronoi diagrams based on different metrics of distance aside from Euclidean distance, while also providing some more insight into how we can apply Voronoi diagrams within other fields.

Real-World Applications

Some areas that utilize Weighted Voronoi Diagrams include:

Geographical Information Systems: Determine aspects of human geography at cities
Economic/Infrastructure modelling: Determine locations for industry or services
Crystallography: Create models of crystals growing at various times
Art: Generate stipple drawings within computer programs

Project Code Repository

Link to the GitHub repository

--- title: "Power Diagrams: Exploration on Weighted Voronoi" author: - name: Batsambuu Batbold - name: Christopher Enberg - name: Blake Kell date: today fontsize: 1.2em format: html: theme: cosmo toc: true toc_float: true toc_depth: 3 self-contained: true code-tools: true code-fold: true jupyter: python3 --- ## Introduction This project explores a different version of a Voronoi Diagram: what happens when the sites are not all treated equally? In many real-world scenarios, locations have different levels of "size" or "power." A large hospital serves a wider area than a small clinic, or a hypermarket offers a wider range of options than a small grocery store. To model this, our project explores **Weighted Voronoi Diagrams**, which give weight to the sites according to their importance. We mostly use *Euclidean* distance when constructing a Voronoi Diagram, which assumes the weights of the sites are equal. To move beyond this, we must give away Euclidean distance and consider another type of distance measurement that takes the different weights of the sites into account. Out of such variations, we will focus on the **Power Diagram**, which is based on the **Power** of a point. ## Power Diagrams ### 1. The Power of a Point The power of a point $P$ with respect to a circle $\omega$ with center $O$ and radius $r$ is defined as: $$ \text{Pow}_\omega(P) = OP^2 - r^2 $$ Thus, if we think of the sites as centers of circles and the weights as their radii, then we can use the power of a point as our "distance" between the point and the site. Here, notice that $OP^2$ is the squared Euclidean distance between the site and a point. A bigger radius (weight) reduces this "distance" by subtracting a larger value, which gives the site more range. For example (Figure $1$), if we have two sites with different weights and a point at an equal Euclidean distance from each site, the point will belong to the site with a larger radius (the larger weight). ![$\text{Figure } 1$: Point $P$ is at an equal Euclidean distance $d$ from both sites $O_1$ and $O_2$. Because the radius (weight) $r_2$ is greater than $r_1$, $P$'s "power distance" to $O_2$ is smaller, and it belongs to the red site's region.](figures/fig1.png){width="50%"} ### 2. The Radical Axis In a standard Voronoi diagram, the Voronoi edges are the perpendicular bisector between two sites because that's where Euclidean distances are equal. Similarly, we define the edges of a Power Diagram as the set of points where the power is equal for two circles: $$ \text{Pow}_{\omega_1}(P) = \text{Pow}_{\omega_2}(P) $$ This set of points is called the **Radical Axis** of the circles. The following two theorems about the Radical Axis demonstrate why this is such a robust choice. :::{.callout-note title="Radical Axis Theorem"} Let $\omega_1$ and $\omega_2$ be circles with distinct centers $O_1$ and $O_2$. The radical axis of $\omega_1$ and $\omega_2$ is a straight line perpendicular to $O_1O_2$. ![$\text{Figure } 2$: The radical axis (green line) represents the set of points with equal power to $\omega_1$ and $\omega_2$. As the theorem states, this axis is a straight line and is perpendicular to the line of centers $O_1O_2$ (gray dashed line).](figures/fig2.png){width="50%"} <details> <summary>Click to see Proof</summary> Let $P = (x, y)$ be any point on the radical axis. Let the centers be $O_1 = (x_1, y_1)$ and $O_2 = (x_2, y_2)$, with radii $r_1$ and $r_2$. By the definition of the radical axis, the power is equal for both circles: $$ \begin{align} \text{Pow}_{\omega_1}(P) &= \text{Pow}_{\omega_2}(P) \\ \Rightarrow (x - x_1)^2 + (y - y_1)^2 - r_1^2 &= (x - x_2)^2 + (y - y_2)^2 - r_2^2 \end{align} $$ After expanding the squared terms: $$(x^2 - 2xx_1 + x_1^2) + (y^2 - 2yy_1 + y_1^2) - r_1^2 = (x^2 - 2xx_2 + x_2^2) + (y^2 - 2yy_2 + y_2^2) - r_2^2$$ Notice that the $x^2$ and $y^2$ terms on both sides cancel out, leaving a linear equation. $$ \begin{align} - 2xx_1 + x_1^2 - 2yy_1 + y_1^2 - r_1^2 = - 2xx_2 + x_2^2 - 2yy_2 + y_2^2 - r_2^2 \\ \Rightarrow 2(x_2 - x_1)x + 2(y_2 - y_1)y + (x_1^2 + y_1^2 - r_1^2 - x_2^2 - y_2^2 + r_2^2) = 0 \end{align} $$ Since $O_1$ and $O_2$ are distinct, at least one of $(x_2 - x_1)$ or $(y_2 - y_1)$ is non-zero. Thus, the above equation is one of a **straight line**. Furthermore, the slope of this line is: $$m_{\text{axis}} = \frac{-2(x_2 - x_1)}{2(y_2 - y_1)} = -\frac{x_2 - x_1}{y_2 - y_1}$$ The slope of the line of centers $O_1O_2$ is: $$m_{\text{centers}} = \frac{y_2 - y_1}{x_2 - x_1}$$ It follows that the product of the slopes is $m_{\text{axis}} \times m_{\text{centers}} = -1$. Therefore, the radical axis is **perpendicular** to the line of centers. $\blacksquare$ </details> ::: This means that, just like a perpendicular bisector, the radical axis also divides the plane into two half-planes. :::{.callout-note title="Radical Axis Concurrence Theorem"} The three pairwise radical axes of three circles concur at a point, called the **Radical Center**. ![$\text{Figure } 3$: The three pairwise radical axes (green, orange, and purple lines) of the circles $\omega_1$, $\omega_2$, and $\omega_3$ are all concurrent (intersect) at a single point, which we call the **Radical Center**.](figures/fig3.png){width="50%"} <details> <summary>Click to see Proof</summary> Let the three circles be $\omega_1$, $\omega_2$, and $\omega_3$. Let $L_{12}$ be the radical axis of $\omega_1$ and $\omega_2$. By definition, for any point $P \in L_{12}$, we have: $$\text{Pow}_{\omega_1}(P) = \text{Pow}_{\omega_2}(P)$$ Let $L_{23}$ be the radical axis of $\omega_2$ and $\omega_3$. For any point $P \in L_{23}$: $$\text{Pow}_{\omega_2}(P) = \text{Pow}_{\omega_3}(P)$$ Now, consider the point $P_{\text{center}}$ where $L_{12}$ and $L_{23}$ intersect. (We can assume the general position where they are not parallel). Since $P_{\text{center}} \in L_{12}$, we know: $$\text{Pow}_{\omega_1}(P_{\text{center}}) = \text{Pow}_{\omega_2}(P_{\text{center}})$$ Since $P_{\text{center}} \in L_{23}$, we also know: $$\text{Pow}_{\omega_2}(P_{\text{center}}) = \text{Pow}_{\omega_3}(P_{\text{center}})$$ By the transitive property, it follows that: $$\text{Pow}_{\omega_1}(P_{\text{center}}) = \text{Pow}_{\omega_3}(P_{\text{center}})$$ Therefore, the intersection point $P_{\text{center}}$ *must* also be on the third radical axis, $L_{13}$, which follow that all three lines pass through the same point. $\blacksquare$ </details> ::: Again, this theorem gives us the position of the Voronoi vertices. Ultimately, these two theorems suggest that the resulting power diagram will have a similar regional structure to a regular Voronoi diagram. ### 3. The Power Diagram More formally, we define the **Power region $\text{Pow}(s)$** of a site $s \in S$ with a weight of $r_s$ as: $$ \begin{align*} \text{Pow}(s) = \{x \in \mathbb{R}^2 \ | \ \text{Pow}_{\omega_s}(x) \le \text{Pow}_{\omega_q}(x) \text{ for all } q \in S \}, \\ \text{ where } \omega_i \text{ is the circle centered at } i \text{ with radius of } r_i \end{align*} $$ Thus, the Power diagram is a collection of these regions. To explore the properties of the power diagram, we generate the Power Diagrams for a set of sites. ## Algorithm Below is the main idea of the algorithm for constructing a power diagram: ```{python} #| eval: false #| code-fold: false #| label: alg-delaunay #| code-summary: "Pseudocode: Weighted Delaunay" FUNCTION weighted_delaunay(input_points): # 1. Initialization # Create a bounding triangle that is guaranteed to contain all input points. super_triangle = CREATE_SUPER_TRIANGLE(input_points) # The triangulation starts with just this single, large triangle. triangulation = [super_triangle] # 2. Incremental Insertion Loop # Process each site one by one, adding it to the triangulation. FOR EACH point IN input_points: bad_triangles = [] # Triangles whose power circle contains the point # a. Find all "bad" triangles FOR EACH triangle IN triangulation: IF point IS INSIDE triangle.power_circle(): ADD triangle TO bad_triangles # b. Find the boundary of the polygonal cavity boundary_edges = [] FOR EACH triangle IN bad_triangles: FOR EACH edge OF triangle: IF edge IS NOT SHARED by any other triangle in bad_triangles: ADD edge TO boundary_edges # c. Remove bad triangles and re-triangulate the cavity REMOVE all triangles in bad_triangles FROM triangulation FOR EACH edge IN boundary_edges: new_triangle = CREATE_TRIANGLE(edge.vertex1, edge.vertex2, point) ADD new_triangle TO triangulation # 3. Cleanup # Remove any triangles from the final list that are connected to the # vertices of the initial super-triangle. final_triangulation = [] FOR EACH triangle IN triangulation: IF triangle DOES NOT SHARE vertices with super_triangle: ADD triangle TO final_triangulation # 4. Return the result RETURN final_triangulation ``` The full `Python` implementation, including the unweighted Voronoi diagram and the code generating the figures below, is available in the GitHub repository linked at the bottom of this page. ### Visual Demonstration ![$\text{Figure } 4$: Comparison between unweighted and weighted Voronoi diagrams](figures/unweighted_vs_weighted.png){width="100%"} ### Observation From the figures above, we can see one of the main differences between Standard Voronoi Diagrams and Weighted Voronoi diagrams: Voronoi regions no longer require a site from $S$ to be located inside each one. Depending on the weights of nearby sites and hoe close they are to one another, Voronoi regions within the Power Diagram can possibly contain either no or multiple sites of $S$. If we consider weights as some sort of popularity or overall size, this phenomenon starts to make more sense - If you're in range of a site that can accommodate more of your needs, you're more likely to go to that site even if there are smaller ones closer to you. ## Conclusion ### Summary In this project, we have discussed what it means to create a Power diagram, and how their construction is equivalent to a Voronoi diagram. We adapted a standard Voronoi region algorithm to utilize this new measure, and analyzed how the two diagrams differ from one other. This allows us to better understand how we can adapt Voronoi diagrams based on different metrics of distance aside from Euclidean distance, while also providing some more insight into how we can apply Voronoi diagrams within other fields. ### Real-World Applications Some areas that utilize Weighted Voronoi Diagrams include: * Geographical Information Systems: Determine aspects of human geography at cities * Economic/Infrastructure modelling: Determine locations for industry or services * Crystallography: Create models of crystals growing at various times * Art: Generate stipple drawings within computer programs --- ## Project Code Repository [**Link to the GitHub repository**](https://github.com/BaSaBu1/Power-Diagram)