Voronoi diagram

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

Voronoi diagrams are 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. In technology, they are used in computer graphics, robot path planning, and creating art patterns.

The idea behind Voronoi diagrams was first explored by a mathematician named Georgy Voronoy. Sometimes they are also called Voronoi tessellations, Voronoi decompositions, or Dirichlet tessellations, after another scientist named Peter Gustav Lejeune Dirichlet. Voronoi diagrams are a powerful tool for understanding space 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 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 like these 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 sick people lived closer to one water pump.

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.

Examples

Voronoi diagrams can make interesting patterns from sets of points.

In two dimensions, points arranged in a triangular pattern make a honeycomb of hexagons. Points arranged in a square pattern make a pattern of squares.

In three dimensions, a simple cubic lattice makes a cubic honeycomb. Other point arrangements can make different shapes.

These patterns show how Voronoi diagrams can create organized and beautiful designs.

Higher-order Voronoi diagrams

A normal Voronoi diagram divides space into areas closest to single points. Higher-order Voronoi diagrams look at areas where a group 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 changed in many ways. They can use different ways to measure distance, like the Manhattan distance, which can make the shapes of the regions more complex. There are also weighted Voronoi diagrams, where points have values that change how the regions look. Some regions might even be empty in these cases.

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

Applications

Voronoi diagrams are useful in many areas. In hydrology and weather studies, they help show how rain falls over an area.

In biology, they show how cells and bones are arranged. In epidemiology, a man named John Snow used them to study a sickness in London long ago. He showed how dirty water helped spread the sickness. In engineering, they help us understand metals. In robotics, they help robots move without bumping into each other. In computer graphics, they help make pictures look real. In networking, they help us understand how well our wireless network works.

Algorithms

There are several smart ways to make Voronoi diagrams. One method, called Fortune's algorithm, can build a Voronoi diagram from a set of points very well. 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. This slowly creates a special kind of Voronoi diagram where each point is right in the middle of its own region.

Voronoi in 3D

Voronoi diagrams can be made in three dimensions too. These are called Voronoi meshes. They split space into areas based on the closest points, just like they do on a flat surface.

Think of these 3D Voronoi meshes as shapes made from random points in space. Each point has a shape called a convex polyhedron around it. Pictures of these meshes show how they look with different settings, like making them partly see-through to see the points inside.