Feeds:
Posts

## Archive for December, 2008

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 $\mathcal{N}$ dimensions. The Voronoi diagram is a tessellation, or a tiling. A tiling of a plane is simply a collection of plane figures that fills the plane with no overlaps and no gaps in between. This idea can ofcourse be extended to $\mathcal{N}$ dimensions, but for simplicity let us stick with 2 dimensions.

[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 $n$ distinct points that we call sites as $\mathcal{P}$. i.e $\mathcal{P}=\{P_1, P_2\ldots, P_n\}$

>> We may then define the Voronoi Diagram of P as a collection $\mathcal{V}=\{V_1,V_2,\ldots, V_n\}$ of subsets of the plane. These subsets are called as Voronoi Regions. Each point in $V_i$ is such that it is closer to $\mathcal{P}_i$ than any other point in $\mathcal{P}$.

To be more precise:

A point $Q$ lies in the Voronoi Region corresponding to a site $P_i \in \mathcal{P}$ if and only if –

$Euclidean\_Distance(Q,P_i) < Euclidean\_Distance(Q,P_j)$ for each $P_i \neq P_j$

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 $\mathcal{P}$.

We can say that $\mathcal{V(P)}$ is the Voronoi Transform, that transforms a set of discrete points (sites) into a Voronoi Diagram.

———-

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“.

[6] Golan Levin, “Segmentation and Symptom

———-

Applets:

2. Bubble Harp.

———-

———-

Onionesque Reality Home >>

## Just Keep Walking

This is a post surely uncharacteristic to this blog. And I just might delete it.

I was just scanning some links on my computer and I would like to share a one minute video that carries an important message. We all know that (the message). However I think the manner in which a message is put across can have a much bigger impact. Isn’t it?

I can achieve immortality by not wearing out. You can achieve immortality, by doing just one great thing – Just Keep Walking.

This is a truly incredible ad, it also reminds me of Isaac Asimov’s The Bicentennial Man at one level.

Life’s hard? And life’s not hard, life is all about pursuit.

Life is pursuit. Life and some of our pursuits in life just like science are Onionesque (like peeling away an onion at the end of which there is a promised or expected solution. The onion might be “infinite” layered or it just might be “finite” ).

Life is something like a stochastic optimization algorithm ;-) with a very very large number of runs. It is not guaranteed you would complete those runs (that is, if the run-time exceeds the time you have), however if you do, it might not be the best solution to the optimization problem, and unfortunately this problem is non-convex (and I can’t prove it ;-). If that is the case, you simply need to re-run and just keep walking and enjoy the pursuit.

Please note, that it is not my intention to argue on the ethical issues concerning the expected blurring lines between truly intelligent robots and humans by posting this ad. It is another matter that I think it is going to happen either way.

PS: I don’t drink, not even socially. It is not my intention to advertise for the mentioned alcohol brand in this advertisement. Though I do think the ad is great.

Onionesque Reality Home >>

## Personal and Historical Prespectives of Hans Bethe

I recently discovered a series of three lectures by the legendary physicist Hans Bethe given in 1999. Bethe was a professor at  Cornell University almost all his life and these lectures given at age 93 had been made public by the University quite a while ago.

[Hans Bethe at the blackboard at Cornell in 1967: Image Source and Copyright – Cornell University ]

These lectures are on the Quantum theory for expert and the non- expert alike. Due to some engagements I am yet to view them, however I am still posting them as I am sure these as given by Bethe himself would be great.

From the Cornell University Webpage for these lectures:

IN 1999, legendary theoretical physicist Hans Bethe delivered three lectures on quantum theory to his neighbors at the Kendal of Ithaca retirement community (near Cornell University). Given by Professor Bethe at age 93, the lectures are presented here as QuickTime videos synchronized with slides of his talking points and archival material.

Intended for an audience of Professor Bethe’s neighbors at Kendal, the lectures hold appeal for experts and non-experts alike. The presentation makes use of limited mathematics while focusing on the personal and historical perspectives of one of the principal architects of quantum theory whose career in physics spans 75 years.

A video introduction and appreciation are provided by Professor Silvan S. Schweber, the physicist and science historian who is Professor Bethe’s biographer, and Edwin E. Salpeter, the J. G. White Distinguished Professor of Physical Science Emeritus at Cornell, who was a post-doctoral student of Professor Bethe.

Introduction

View Introduction (Quick Time Required)

The introduction has been given by Edwin E. Salpeter and Silvan S. Schweber.

Lecture 1

View Lecture 1 (Quick Time Required)

Lecture 2

View Lecture 2 (Quick Time Required)

Lecture 3

View Lecture 3 (Quick Time Required)

Appreciation

View Appreciation (Quick Time Required)

Note: All the images above and also the text giving an introduction to the lectures are a copyright of Cornell. Please comply with the terms of use associated with them.

Onionesque Reality Home >>