Voronoi diagram

In mathematics, a Voronoi diagram is a special way to divide a space into regions based on distance. Imagine you have a few points scattered on a piece of paper. For each point, you can draw a region around it that includes every spot on the paper that is closer to that point than to any other point. These regions are called Voronoi cells, and the whole picture you draw is a Voronoi diagram.

Voronoi diagrams are very useful in many areas of science and technology. They help scientists understand how things spread out in space, like how plant roots grow or how water flows through soil. In technology, they are used in things like computer graphics, robot path planning, and even in creating beautiful patterns in art.

The idea behind Voronoi diagrams was first explored by a mathematician named Georgy Voronoy, so we name these diagrams after him. Sometimes they are also called Voronoi tessellations, Voronoi decompositions, or Dirichlet tessellations, after another scientist named Peter Gustav Lejeune Dirichlet. No matter what you call them, Voronoi diagrams are a powerful tool for understanding how space can be organized around points.

Simplest case

In the simplest case, we start with a set of points on a flat surface, like dots on a piece of paper. Each point has an area around it called a "cell." This cell includes all the places that are closer to that point than to any other point. The edges of these cells are where two points are equally close. Where three or more cells meet, we get a point that is equally close to all of them. These cells are always shaped like simple, smooth polygons.

Formal definition

The Voronoi diagram is a way to divide space into regions based on distance. Imagine you have several points, called "sites." For each site, there is a region around it that contains all the points that are closer to it than to any other site. This region is called a Voronoi cell.

In simple terms, if you pick any point inside a Voronoi cell, it will be closer to the site that created that cell than to any other site. This idea can be used in many areas, like maps or science, to show how things are spread out or organized in space.

Illustration

Imagine you have several shops in a city. If people always choose the shop that is closest to them, we can use a Voronoi diagram to guess how many customers each shop might have. Each shop has an area on the map where it is the nearest shop — this area is called a Voronoi cell.

We can measure distances between shops in different ways. The most common way is called Euclidean distance, which is the straight-line distance. Another way is called Manhattan distance, which adds up the horizontal and vertical distances instead. These different ways of measuring distance create different-looking Voronoi diagrams.

Properties

A Voronoi diagram is closely connected to another mathematical idea called a Delaunay triangulation. They are like two sides of the same coin when you start with the same set of points. In a Voronoi diagram, the closest pair of points you can find will always be next to each other in the diagram.

Voronoi diagrams also have some special properties depending on the space they are in. For example, in a flat, two-dimensional space, points that are on the outer edge of all the points will have Voronoi cells that share a side that goes on forever. These diagrams are also stable, meaning that small changes to the points only cause small changes to the diagram's shape, under certain conditions.

History and research

Voronoi diagrams have a long history. People used ideas similar to these diagrams as early as 1644. In 1850, a mathematician named Peter Gustav Lejeune Dirichlet used them in his work. During a cholera outbreak in 1854, a doctor named John Snow used a diagram to show that most people who got sick lived closer to one water pump than any other.

These diagrams are named after Georgy Feodosievych Voronoy, who studied them in detail in 1908. In weather studies, they are sometimes called Thiessen polygons, named after Alfred H. Thiessen, who used them in 1911 to estimate rainfall from different locations.

Examples

Voronoi tessellations of regular lattices of points create many well-known patterns. In two dimensions, a regular triangular lattice forms a regular honeycomb of hexagons, while a square lattice results in a regular pattern of squares. In three dimensions, a simple cubic lattice produces a cubic honeycomb, and other lattices create different shapes like trapezo-rhombic dodecahedra or rhombic dodecahedra.

For points arranged in specific patterns, we can get rectangular tiles where the points might not be at the center of each tile. These patterns show how Voronoi diagrams can create beautiful and organized designs from sets of points.

Higher-order Voronoi diagrams

A normal Voronoi diagram divides space into areas closest to single points. But higher-order Voronoi diagrams look at areas where a set of points are the nearest neighbors. For example, a 2nd-order Voronoi diagram shows areas where two specific points are the closest.

These diagrams can be built step by step. To create a higher-order diagram, we start with a lower-order one and then replace each area with a new Voronoi diagram. One special type is the farthest-point Voronoi diagram, which shows areas where a point is the farthest from all others. This diagram only includes points on the outer edge of the group, called the convex hull. Each area in this diagram belongs to one of these outer points.

Generalizations and variations

Voronoi diagrams can be adapted in many ways. They can use different ways to measure distance, like the Manhattan distance, which might make the shapes of the regions more complex. There are also weighted Voronoi diagrams, where points have weights that change how the regions are formed. Some regions might even be empty in these cases.

Voronoi diagrams are connected to other geometric ideas, such as the medial axis, which is used in image processing and recognizing shapes.

Applications

Voronoi diagrams have many useful applications across different fields. In meteorology and hydrology, they help calculate average precipitation by determining the influence area of each weather station.

In biology, they model how cells and bone structures organize themselves. In epidemiology, they were used by John Snow to study the 1854 Broad Street cholera outbreak in London, showing links between water pumps and disease spread. In engineering, they help in materials science to represent metallic microstructures, and in robotics to plan paths for multiple robots. In computer graphics, they create textures and shattering effects, while in networking, they help determine wireless network capacity.

Algorithms

There are several smart ways to create Voronoi diagrams. One method, called Fortune's algorithm, can build a Voronoi diagram from a set of points quite efficiently. Another way uses something called a Delaunay triangulation and then flips it to get the Voronoi diagram.

Some algorithms, like Lloyd's algorithm, use Voronoi diagrams as part of a bigger process. These methods move the starting points to better spots inside their areas, slowly creating a special kind of Voronoi diagram where each point is right in the middle of its own region.

Voronoi in 3D

Voronoi diagrams can also be created in three dimensions, forming what are called Voronoi meshes. These meshes divide space into regions based on the closest points, similar to how they work on a flat surface.

You can imagine these 3D Voronoi meshes as being made from random points in space, creating shapes like convex polyhedra around each point. Pictures of these meshes show how they look with different settings, such as making them partly see-through to view the points inside.