Imagine you’re organizing a pizza party for your friends. Each friend loves a different topping, so you scatter their favorite toppings (like pepperoni, pineapple, and mushrooms) on a giant pizza like dots. Now, you want to draw lines on the pizza so each part is closest to one topping more than any other. This “territory map” for the toppings is basically a Voronoi diagram!
In the picture above, see how each topping has its own “zone” where every bite is closer to that topping than any other. These zones are the Voronoi cells, and the lines that separate them are called Voronoi edges.
Cool, right? Voronoi diagrams aren’t just for pizza toppings, though. They’re used in science to analyze animal territories, in art to create cool patterns, and even in city planning to figure out which school district each house belongs to! So next time you see a honeycomb or a mosaic, remember, it might just be a Voronoi diagram in disguise!
Remember, Voronoi diagrams are like dividing up a space based on who’s the “closest neighbor” at every point. So, just think of pizza or any other scenario where you have different “centers” claiming their turf, and you’ll get the basic idea!
Voronoi diagram in life
Voronoi diagrams aren’t just confined to the realm of mathematics. Look around you, and you’ll find their fingerprints everywhere:
- Nature’s artistry: Honeybees, guided by an instinctual understanding of Voronoi principles, construct their hexagonal hives, maximizing efficiency and space.
- Artistic inspiration: From mosaic art to stained glass windows, artists have long embraced Voronoi patterns to create stunning visual works.
- Urban planning: City planners utilize Voronoi diagrams to map school districts, optimize public transportation routes, and even analyze crime patterns.
So, the next time you gaze at a honeycomb, admire a mosaic, or navigate your city streets, remember the hidden hand of Voronoi diagrams at play. These geometric gems are a testament to the beauty and elegance of mathematics, weaving their magic into the very fabric of our lives.
This is just a taste of the captivating world of Voronoi diagrams. Get ready to delve deeper into their secrets, explore their applications, and discover the hidden geometry that shapes our world in ways we never imagined!
Mathematical definition
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. It can be classified also as a tessellation. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set’s Delaunay triangulation.
The Voronoi diagram is named after mathematician Georgy Voronoy, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet). Voronoi cells are also known as Thiessen polygons, after Alfred H. Thiessen.[1][2][3] Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology, but also in visual art.
The simplest case
In the simplest case, shown in the first picture, we are given a finite set of points in the Euclidean plane. In this case each site is one of these given points, and its corresponding Voronoi cell consists of every point in the Euclidean plane for which is the nearest site: the distance to is less than or equal to the minimum distance to any other site . For one other site , the points that are closer to than to , or equally distant, form a closed half-space, whose boundary is the perpendicular bisector of line segment . Cell is the intersection of all of these half-spaces, and hence it is a convex polygon.[6] When two cells in the Voronoi diagram share a boundary, it is a line segment, ray, or line, consisting of all the points in the plane that are equidistant to their two nearest sites. The vertices of the diagram, where three or more of these boundaries meet, are the points that have three or more equally distant nearest sites.
Mathematical definition
Let be a metric space with distance function . Let be a set of indices and let be a tuple (indexed collection) of nonempty subsets (the sites) in the space . The Voronoi cell, or Voronoi region, , associated with the site is the set of all points in whose distance to is not greater than their distance to the other sites , where is any index different from . In other words, if denotes the distance between the point and the subset , then
The Voronoi diagram is simply the tuple of cells . In principle, some of the sites can intersect and even coincide (an application is described below for sites representing shops), but usually they are assumed to be disjoint. In addition, infinitely many sites are allowed in the definition (this setting has applications in geometry of numbers and crystallography), but again, in many cases only finitely many sites are considered.
In the particular case where the space is a finite-dimensional Euclidean space, each site is a point, there are finitely many points and all of them are different, then the Voronoi cells are convex polytopes and they can be represented in a combinatorial way using their vertices, sides, two-dimensional faces, etc. Sometimes the induced combinatorial structure is referred to as the Voronoi diagram. In general however, the Voronoi cells may not be convex or even connected.
In the usual Euclidean space, we can rewrite the formal definition in usual terms. Each Voronoi polygon is associated with a generator point . Let be the set of all points in the Euclidean space. Let be a point that generates its Voronoi region , that generates , and that generates , and so on. Then, as expressed by Tran et al,[7] “all locations in the Voronoi polygon are closer to the generator point of that polygon than any other generator point in the Voronoi diagram in Euclidean plane”.
General voronoi diagram
Traditional Voronoi diagrams rely on a fundamental concept: measuring the distance between points. Typically, we use Euclidean distance, the straight-line distance familiar from geometry class. Just imagine two pins stuck on a map, and the shortest path between them, measured with a ruler, represents their Euclidean distance.
This concept forms the backbone of traditional Voronoi diagrams. Around each point (called a “site” or “generator”), we draw a region encompassing all points closer to that site than any other. These regions, called Voronoi cells, form a tessellation, like a colorful jigsaw puzzle that perfectly covers the plane.
But the story doesn’t end there! Euclidean distance is just one way to measure “closeness.” What if we used other metrics? like manhattan distance.
If we were to plot Voronoi diagrams using 20 points on both of these metrics, they would look like this: