Power Diagram

The simple question of what is 'closest' gives rise to one of geometry's most elegant structures: the Voronoi diagram, a mosaic that partitions space based on proximity. However, this model assumes all points of interest are equal. What happens when they are not? This article addresses this limitation by exploring the Power Diagram, a profound generalization that incorporates the 'weight' or 'influence' of each point. By shifting from simple distance to a more sophisticated measure, the Power Diagram offers a more realistic model for countless real-world scenarios. In the following chapters, we will first unravel the "Principles and Mechanisms," tracing the evolution from the nearest-neighbor rule of Voronoi diagrams to the weighted influence of Power Diagrams. Subsequently, the section on "Applications and Interdisciplinary Connections" will demonstrate how this single geometric idea provides a unifying language to describe structure in diverse fields, from solid-state physics to quantum chemistry.

Imagine you're standing in a city, and you want to find the closest library. A simple question, but if you were to color a map of the city, assigning to each point the color of its nearest library, you'd be creating a beautiful and deeply mathematical object. This simple idea of partitioning space based on "what's closest" is the gateway to a fascinating world of geometric structures, a world we're about to explore. We'll start with the simplest rules and, by asking "what if?", we will uncover surprising and elegant generalizations that have profound applications, from designing materials to analyzing complex networks.

Let's formalize our library problem. Suppose we have a set of special points, which we'll call ​​sites​​, scattered across a flat plane. These could be our libraries, cell phone towers, or even the positions of atoms in a crystal. For any spot on the plane, we can ask: which site is it closest to?

The collection of all spots that are closer to a particular site, say site $A$, than to any other site, forms the "territory" of site $A$. This territory is called the ​​Voronoi cell​​ of $A$. If you do this for every site, you partition the entire plane into a mosaic of these cells. This beautiful mosaic is the ​​Voronoi diagram​​.

What do the borders of these territories look like? Consider just two sites, $A$ and $B$. The set of points that are exactly equidistant from $A$ and $B$ forms a straight line—the perpendicular bisector of the segment connecting them. Since the boundary of a Voronoi cell is defined by this condition of being equidistant to two (or more) sites, the edges of the Voronoi diagram are all straight line segments. Each cell is a convex polygon, a kingdom ruled by its central site.

This principle is everywhere. It describes the growth patterns of crystals, the territories of animals, and the market areas of competing stores. It's nature's way of dividing up space based on proximity.

Now, let’s look at our map of Voronoi cells and ask a different question. Which sites are "neighbors"? A natural definition is that two sites are neighbors if their Voronoi cells share a common border. If we draw a line connecting every pair of neighboring sites, a new picture emerges from the old one. We get a network of triangles that covers our sites. This new network is the ​​Delaunay triangulation​​.

This relationship is a classic example of ​​geometric duality​​. It’s like looking at the same object from two perfectly complementary perspectives. The features of one diagram correspond directly to features in the other:

• Each ​​site​​ (a vertex in the Delaunay triangulation) corresponds to a ​​cell​​ in the Voronoi diagram.

• Each ​​edge​​ connecting two sites in the Delaunay triangulation corresponds to the ​​edge​​ their cells share in the Voronoi diagram. In fact, the Delaunay edge is perfectly perpendicular to the Voronoi edge.

• Each ​​triangle​​ in the Delaunay triangulation corresponds to a ​​vertex​​ in the Voronoi diagram—the point where the three corresponding cells meet.

There’s a hidden rule that governs which triangles are allowed in a Delaunay triangulation, known as the ​​empty circle property​​. If you draw a circle that passes through the three vertices of any Delaunay triangle, that circle's interior will contain no other sites. This "empty circle" is centered precisely at the corresponding Voronoi vertex, the meeting point of the three territories. This elegant property is not just a curiosity; it's the reason Delaunay triangulations are so useful in creating high-quality meshes for simulations, as they tend to avoid long, skinny triangles.

Our simple model assumes all sites are created equal. But what if they aren't? What if one library is a huge, multi-story national archive and another is a tiny mobile book van? The simple "closest-distance" rule doesn't seem to capture the difference in their influence. We need a new way to measure "attraction" that accounts for a site's intrinsic "power" or "size".

Let's upgrade our sites from dimensionless points to circles, each with a center $\mathbf{c}_i$ and a radius $r_i$. The radius can represent the size, influence, or some other intrinsic weight of the site. Now, how do we define the "distance" from an arbitrary point $\mathbf{x}$ to one of these circle-sites?

We introduce a new measure called the ​​power distance​​. For a point $\mathbf{x}$ and a site $i$ (a circle with center $\mathbf{c}_i$ and radius $r_i$), the power distance is defined as:

This might look a bit abstract, but it has a beautiful geometric meaning. If the point $\mathbf{x}$ is outside the circle, $\pi_i(\mathbf{x})$ is positive and is exactly the squared length of the tangent line from $\mathbf{x}$ to the circle. If $\mathbf{x}$ is on the circle, the power is zero. If $\mathbf{x}$ is inside, the power is negative. So, this isn't a distance in the usual sense (it can be negative!), but it's a wonderful measure of a point's relationship to a circle. We can think of the term $w_i = r_i^2$ as the ​​weight​​ of the site.

With our new rule—the power distance—we can play the same territory game again. For any point $\mathbf{x}$, we find the site that has the smallest power distance to it. The region of points "loyal" to site $i$ is its power cell. The collection of all these cells is the ​​Power Diagram​​.

And here comes the first beautiful surprise. What do the boundaries between these new power cells look like? Let's find the set of points $\mathbf{x}$ that have equal power distance to two sites, $i$ and $j$:

If we expand the squared norm terms (e.g., $\lVert \mathbf{x} - \mathbf{c}_i \rVert^2 = (\mathbf{x} - \mathbf{c}_i) \cdot (\mathbf{x} - \mathbf{c}_i) = \lVert \mathbf{x} \rVert^2 - 2 \mathbf{x} \cdot \mathbf{c}_i + \lVert \mathbf{c}_i \rVert^2$), you'll notice that the $\lVert \mathbf{x} \rVert^2$ terms on both sides of the equation cancel out. What remains is a linear equation in the coordinates of $\mathbf{x}$. This means the boundary is still a straight line! This is remarkable. By choosing our "distance" function carefully, we have generalized our problem to include weighted sites while preserving the simple, linear nature of the boundaries.

Just as before, this Power Diagram has a dual. If we connect the centers of all sites whose power cells share a border, we get a triangulation known as the ​​regular triangulation​​ or weighted Delaunay triangulation. The "empty circle" property also generalizes. A triangle of sites $(i, j, k)$ exists in the regular triangulation if and only if there's a special circle that intersects all three site-circles at right angles (orthogonally), and no other site's power distance to the center of this orthogonal circle is smaller.

This new game of power has a strange and fascinating twist that was impossible in the simple Voronoi world. In a regular Voronoi diagram, every site is guaranteed to have some territory, no matter how hemmed in it is by its neighbors. In a Power Diagram, this is not true. A site can have an empty cell—it can possess zero territory!

Imagine a small circle (a low-weight site) surrounded by much larger, more powerful circles. Its influence might be so completely overshadowed by its neighbors that there is not a single point in the plane where it is the most "powerful". Its power cell is an empty set. Such a site is called a ​​hidden site​​. It exists, but it has no kingdom. This is a profound consequence of changing our distance rule; it introduces a competitive aspect where some sites can be completely squeezed out.

How can we be sure of all this? How can we visualize this complex interplay of weights and distances? There is an astonishingly elegant trick, a classic piece of mathematical insight. We can understand it all by lifting the problem into a higher dimension. Imagine our 2D plane is the floor of a 3D room. We can lift each site's center $\mathbf{c}_i$ up to a point in 3D space with coordinates $(\mathbf{c}_i, \lVert \mathbf{c}_i \rVert^2 - w_i)$. The height of each lifted point depends on its location and its weight.

Now, imagine stretching a sheet of rubber under all these lifted points. The shape this rubber sheet forms is the "lower convex hull" of the points. If you now look down from above and see which lifted points the rubber sheet touches, the projection of those points and the connections between them back onto the 2D floor is exactly the regular triangulation!

This "lifting map" provides a unified view. The standard Delaunay triangulation is just the special case where all weights $w_i$ are zero. And it gives us a beautiful intuition for hidden sites: a site becomes hidden if its lifted point is not on the lower boundary of the convex hull, but is instead "floating" somewhere inside it, completely shielded from below by the rubber sheet stretched between its more powerful neighbors. This beautiful geometric construction turns a complex algebraic problem into a simple, visual one, revealing the deep unity and elegance underlying the world of Voronoi diagrams and their powerful cousins.

We have spent some time getting to know the power diagram, starting from its simpler cousin, the Voronoi diagram, and adding the crucial concept of "weights." It might seem like a rather abstract piece of geometry. But the real joy in physics, as Richard Feynman would often remind us, is not just in discovering a new rule or a new mathematical trick, but in seeing how that one idea suddenly illuminates a dozen different corners of the universe. The power diagram is just such an idea. Once you have this tool in your hand, you start to see problems everywhere that it can help solve. It provides a common language to describe structure and organization in systems that, on the surface, look completely different. Let us take a tour of some of these applications, from the perfect order of a crystal to the fuzzy, probabilistic world of the electron.

There is perhaps no better example of order in nature than a crystal. At the atomic scale, a crystal is a breathtakingly regular, repeating array of atoms. If we want to understand the properties of a crystalline material, a fundamental first step is to figure out how to divide up the space of the crystal and assign a portion of it to each atom.

For the simplest crystals, known as Bravais lattices, where every atomic site is identical and equivalent, there is a very natural way to do this. For any given atom, we can claim all the points in space that are closer to its center than to any other atom's center. This region is the atom's Voronoi cell, which in the context of solid-state physics is known as the ​​Wigner-Seitz cell​​. These cells, one for each atom, fit together perfectly to tile all of space, like a set of identical, exquisitely shaped 3D tiles. The volume of this cell is fundamental; it is the volume per atom, and it allows us to calculate macroscopic properties like the material's density and its ​​atomic packing factor (APF)​​—the fraction of space actually filled by the atoms modeled as hard spheres.

Now, here is a question to test our geometric intuition. You might think that the number of faces on an atom's Wigner-Seitz cell would simply be its number of nearest neighbors, its "coordination number." For a simple cubic lattice, you would be right. But nature is more subtle. In the very common body-centered cubic (BCC) structure, for example, each atom has 8 nearest neighbors. Yet, its Wigner-Seitz cell is a beautiful 14-faced polyhedron called a truncated octahedron. Where do the extra 6 faces come from? They are defined by the atom's second-nearest neighbors!. This is a wonderful lesson: even in this world of perfect order, the geometric neighborhood can be more complex than the simple metric neighborhood.

The real world, however, is rarely made of just one type of atom. What happens in an alloy, or a chemical compound like salt, where we have atoms of different sizes? A sodium ion is smaller than a chloride ion. Is it fair to draw the boundary plane exactly halfway between them? Surely the larger chloride ion should command a larger region of space. This is precisely where the standard Voronoi diagram, based on a simple "closest-point" rule, breaks down.

And this is where the ​​power diagram​​ makes its grand entrance. By assigning a weight to each atom, typically related to its atomic or ionic radius, the power diagram creates a partition of space that is physically far more meaningful. The boundary is no longer the perpendicular bisector but is shifted toward the smaller atom. It is no longer a question of which atom's center is closest, but a more sophisticated balance of power, so to speak, that accounts for the atoms' inherent sizes. For understanding the structure of any material with multiple, distinct atomic species, the power diagram is not just a curiosity; it is the correct geometric tool for the job.

Perfection is a useful fiction for physicists, but the real world of materials is beautifully messy. Even a simple compound like a perovskite, a class of materials found in everything from high-temperature superconductors to next-generation solar cells, is rarely found in its ideal, high-symmetry form. The neat framework of atoms is often twisted, tilted, and distorted.

This creates a genuine puzzle for scientists: what does it even mean to be a "neighbor"? In a real, distorted perovskite, experimental data might show a central atom having, say, 8 close oxygen neighbors and another 4 that are a bit farther away. A chemist might look at this and declare the coordination number to be 8, focusing on the atoms that form the strongest chemical bonds. However, a purely geometric or topological analysis using a standard Voronoi diagram might find that all 12 of those oxygen atoms are geometric neighbors, each defining a face on the central atom's Voronoi cell.

So, which is it, 8 or 12? The surprising answer is that this is the wrong question to ask. Both numbers are correct; they just represent answers to different questions. One describes the bonding environment, while the other describes the topological environment. This ambiguity is not a failure of our methods, but a reflection of the material's complexity.

Once again, the power diagram offers a more nuanced perspective. By weighting the atoms with their known ionic radii, we can construct a power diagram that often provides a partition that aligns better with chemical intuition. For instance, it might correctly identify the 6 strongly-bonded oxygen neighbors around a small cation in the perovskite structure, effectively "demoting" more distant topological neighbors that are less important chemically. This demonstrates the role of the power diagram as a sophisticated tool in a larger analytical toolkit, helping scientists translate the complex geometry of real materials into chemically meaningful insights.

What if we abandon order entirely? Think of a glass, where atoms are frozen in a jumbled, liquid-like arrangement. There is no repeating lattice, no unit cell. How can we possibly describe such a structure? This is a domain where Voronoi analysis, including the power diagram, becomes truly indispensable.

For materials like metallic glasses, we can compute the Voronoi cell for every single atom in a computer simulation or an experimental model. This provides a rich, local, atom-by-atom description of the disordered packing. We can find the distribution of coordination numbers, the shape of the average atomic environment, and search for hidden structural motifs, like the prevalence of icosahedral (five-fold symmetric) packing that is thought to be a hallmark of the glassy state.

This same logic applies with equal force to the "soft matter" world of colloids, polymers, and foams. Imagine watching microscopic plastic beads suspended in water settling into a dense pile. Using 3D microscopy, scientists can capture a snapshot of this packing. A crucial step in analyzing this image is to identify every bead and partition the space among them. If the beads have even a small variation in size—and in any real experiment, they always do—the standard Voronoi diagram is geometrically incorrect. The ​​power diagram is the essential and correct tool​​ for the job. Only by using a power diagram, weighted by the measured radius of each individual bead, can scientists accurately determine fundamental properties like the distribution of local packing densities and coordination numbers. This kind of analysis is vital for understanding everything from the stability of paint and food products to the self-assembly of novel materials.

So far, our applications have treated atoms as simple spheres. Let us now take a leap into a more abstract, but perhaps even more beautiful, realm. In quantum mechanics, an atom is not a hard ball but a positive nucleus surrounded by a fuzzy, continuous cloud of electron density. Quantum chemists have long sought a principled way to divide this continuous cloud among the atoms in a molecule or crystal, a procedure known as Bader charge analysis. The boundaries in this analysis are defined as "zero-flux surfaces," which can be pictured as watersheds on a topographical map of the electron density. These surfaces are generally complex and curved.

Here lies a truly remarkable and profound connection. In the special, highly symmetric case of a perfect crystal made of identical atoms, these physically-defined Bader surfaces, derived from quantum mechanics, are ​​exactly identical​​ to the simple, flat-faced boundaries of the Wigner-Seitz (Voronoi) cells. A purely geometric construction, born from the elementary question of "who is closest?", perfectly coincides with a partition derived from the Schrödinger equation. It is a stunning instance of the deep unity of scientific principles, where geometry and quantum physics unexpectedly shake hands.

Of course, we must also appreciate the limits of the analogy. As soon as the crystal's symmetry is broken or we introduce different types of atoms, the curved Bader surfaces and the flat faces of a power diagram diverge. The real quantum world is more complex than the simple geometric model. But even then, the power diagram serves as an invaluable reference—a clean, geometric scaffold upon which the more intricate tapestry of quantum reality is woven.

From the perfect grids of a crystal to the jumbled pack of atoms in a glass, from the jostling of colloidal beads to the ethereal clouds of electrons, the elegant idea of partitioning space according to a weighted distance provides a unifying language. It is a testament to the astonishing power of simple geometric ideas to reveal the hidden structure and logic of our world, at all its many scales.