While searching for some methods for face representation in connection with my recent project, I lost the way clicking on some stray links and landed up on some beautiful art work involving Voronoi diagrams. I was aware of art work based on Voronoi diagrams (it kind of follows naturally that Voronoi diagrams can lead to very elegant designs, isn’t it?) but a couple of images on them were enough to re-ignite interest. It was also interesting to see an alternate solution to my problem based on Voronoi diagrams as well. However I intend to share some of the art work I came across.
———-
Before I get to the actual art-work I suppose it would be handy to give a very basic introduction to Voronoi Diagrams with a couple of handy applications.
Introduction: Voronoi diagrams are named after Georgy Voronoy (1868-1908), an eminent Russian/Ukrainian mathematician. A number of mathematicians before Voronoy such as Descartes and Dirichlet have been known to have used them, Voronoy extended the idea to 
[A pavement Tessellation/Tiling]
Definition: A Voronoi diagram is a special kind of a decomposition of a metric space which is determined by a discrete set of points.
Generally speaking for a 2-D case:
>> Let us designate a set of 
>> We may then define the Voronoi Diagram of P as a collection 
To be more precise:
A point 
However it might be the case that there are some points in the plane that might have more than one site that is the closest to it. These points do not lie in either Voronoi Region, but simply lie on the boundary of two adjacent regions. All such points form a skeleton of lines that is called the Voronoi Skeleton of
We can say that 
———-
For more clarity on the above, consider a sample Voronoi Diagram below:
The dots are called the Sites. The Voronoi Regions are simply areas around a site but enclosed by the lines around them. The network of lines is simply the Voronoi Skeleton.
———-
Some Extensions to the above Definition: The above definition which is ofcourse extremely simple can be extended very easily[1] for getting some fun art forms.
Some of these extensions could be as follows [1]:
1. Since each region corresponds to a site, each site can be associated with a color. Hence the Voronoi diagram can be colored accordingly.
2. In the definition the sites were considered to be simply points, we can obtain a variety of figures by allowing the “sites” to be subsets of the plane than just points. We see, that if the sites are defined as simply points, the Voronoi skeleton would always be composed of straight lines. With this change there could be interesting skeletal figures emerging.
3. We could also modify the distance metric from the Euclidean distance to some other to get some very interesting figures.
This just shows the kind of variety of figures that can be generated by just a small change in one aspect of the basic definition.
———-
Constructing a Voronoi Diagram:
Let us forget the extensions that we spoke of for a moment and come back to the basic definition. Looking at the definition it seems constructing Voronoi diagrams is a simple process. And it is not difficult at all. The steps are as follows:
1. Consider a random set of points.
2. Connect ALL of these points by straight lines.
3. Draw a perpendicular bisector to EACH of these connecting lines.
4. Now select pieces that are formed, such that each site (point) is encapsulated.
Voronoi Diagrams can be very easily made by direct commands in both MATLAB and MATHEMATICA.
———-
Voronoi Diagrams in Nature: It is interesting to see how often Voronoi diagrams occur in nature. Just consider two examples:
[Left: Reticulum Plasmatique (Image Source) Right: Polygons on Giraffes]
———-
Uses of Voronoi Diagrams: There are a wide variety of applications of Voronoi diagrams. They are more important then what one might come to believe. Some of the applications are as follows:
1. Nearest Neighbour Search: This is the most obvious application of Voronoi Diagrams.
2. Facility Location: The example that is often quoted in this case is the example of choosing where to place a new Antenna in case of cellular mobile systems and similarly deciding the location of a new McDonalds given a number of them already exist in the city.
3. Path Planning: Suppose one models the sites as obstacles, then they can be used to determine the best path (a path that stays at a maximum distance from all obstacles or sites).
There are a number of other applications, such as in Geophysics, Metrology, Computer Graphics, Epidemiology and even pattern recognition. A very good example that illustrates how they can be used was the analysis of the Cholera epidemic in London in 1854, in which physician John Snow determined a very strong correlation of deaths with proximity to a particular infected pump (specific example from Wolfram Mathworld).
Let’s consider the specific example of path planning [2]. Consider a robot placed in one corner of a room with stuff dispersed around.
Now the best path from the point where the robot is located to the goal would be the one in which the robot is farthest from the nearest obstacle at any point in time. To find such a path, the Voronoi diagram of the room would be required to be found out. Once it is done, the vertices or the skeleton of the Voronoi Diagram provides the best path. Which path ultimately is to be taken can be found out by comparing the various options (alternative paths) by using search algorithms.
Now finally after the background on Voronoi Diagrams let’s look at some cool artwork that i came across. ;-)
———-
Fractals from Voronoi Diagrams:
This I came across on the page of Kim Sherriff[3]. The idea is straightforward to say the least.
It is: To create a fractal, first create a Voronoi diagram from some points, next add more points and then create the Voronoi diagrams inside individual Voronoi Regions. Some sample progression could be like this:
Repeating the above process recursively on the above would give the following Voronoi fractal.
Interestingly, this fractal looks like the structure of a leaf.
The above was repeated in color by Frederik Vanhoutte[4] to get some spectacular results. Also I would highly recommend his blog!
[Voronoi Fractal – Image Source]
I am really going to try this myself, it seems a few hours of work at first sight. Ofcourse I won’t use the code that the author has provided. ;-)
———-
Mosaic Images Using Voronoi Diagrams[5] :
I have not had the time to read this paper. However, I am always attracted by mosaics, and these ones (the ones in the paper) as created using Voronoi Diagrams have an increased coolness quotient for me. Sample this image:
Golan Levin’s[6] experiments in using Voronoi diagrams to obtain aesthetic forms yielded probably even more pleasant results. The ones below give a very delicate look to their subjects.
The tilings that are produced by just mild tweaks to the basic definition of a Voronoi Diagram for a 2-D case that I had talked about earlier can give rise to a variety of tilings. Say like the one below:
Also, today I came across a nice Voronoi Diagram on The Reference Frame:
The diagram is a representation of 17,168 weather stations around the world. Dr Motl illustrates how handy MATHEMATICA is for such things.
Click to Enlarge
———-
References:
[1] Craig Kaplan, “Voronoi Diagrams and Ornamental Design“.
[2] Introduction to Voronoi Diagrams – Example.
[3] Kim Sherriff, “Fractals from Voronoi Diagrams“.
[4] Frederik Vanhoutte, “Voronoi Fractal“.
[5] A Method for creating Mosiac Images using Voronoi Diagrams.
[6] Golan Levin, “Segmentation and Symptom“
———-
Applets:
2. Bubble Harp.
———-
Additional Links:
1. Image Stained Glass using Voronoi Diagrams.
2. Interactive Design of Authentic Looking Mosaics using Voronoi Diagrams.
———-
Onionesque Reality 