Spotted: VoronoiTom

It's not exaclty a surprise to me that many people are exploring Voronoi diagrams. Today, I came across a really cool site - VoronoiTom.

Tom explored countless variantions of the Voronoi diagrams, based on a set of points, arranged in different regular patterns. If you're interested in Voronoi, you must see this. The 3d vizualisations are really nice, but I like his extensive analysis of various 2d Voronoi configurations even more.

Voronoi 3d Explorations

While most of the time Voronoi diagrams are based on (at least seemingly) random set of point, I started to explore some regular patterns.

If you place input points in a regular square grid, the Voronoi diagram is a grid as well. Well, that's not a huge surprise.

If you slide each row of points in a grid for half a distance between the points, you get a honeycomb pattern. That's interesting.

What's the purpose of these games? To understand the relation between input (set of points) and output (Voronoi diagram) better. In my applications, to put it very simply, the former would represent genotype and latter phenotype. Of course, in the evolutionary process I would not control the input points directly, but I somehow sense that it would be beneficial if I understood the Voronoi diagrams as much as possible.

More of Voronoi

I played with "my" Voronoi generator (2d and 3d); here are some screenshots.

Qhull solution

Hmmm... it turned out that the construction of Voronoi diagrams is far from trivial. There are some serious papers out there, and they involved quite a bit of mathematics, to put it mildly.

I started to study the 2d methods first.

The sweep method (java required for demo) seemed so not elegant to me. "Wave front", come on, what's that? :-) There must be a better way.

I found the divide-and-conquer approach, presented by Shamos and Hoey, much more elegant. It can be easily attacked with the object-oriented programming language.

But after some hours of intensive work some concernes began to arise. The algorithm was pretty complex, but I was still in 2d. What would happen in 3d? The complexity would go over the roof. After all, the Voronoi construction itself is not the topic of my research; it's merely a tool and I should spend as little time as possible for it.

I stopped the work with the divide-and-conquer construction of Voronoi and headed for the web again; let's find some more info about 3d Voronoi construction.

My fears that 3d Voronoi construciton is far from trivial were confirmed, when I discovered that two first-class mathematical tools, Mathematica and Mathlab, both use external library Qhull for Voronoi (and related) computations.

Qhull is a powerful software put together by nice people who seemingly allow us to use it freely. It can do convex-hull, Voronoi diagrams and Delaunay triangualtion (which is the dual of Voronoi) in not only 2d and 3d, but even in higher dimensions, at least up to 8d; so there was really no point in competing with it :-)

After a few hours crunching numbers and fighting with academic-style documentation, almost all of my Voronoi computation problems were solved. As a bonus, it turned out that Qhull was lightning fast as well. Happy ending!

Spotted: Evolved Virtual Creatures

This is a must-see for anyone interested in Evolutional Computing (EC). Actually, it's a must-see for everyone.

The Voronoi Addiction

Wow, I found a real jewel. Voronoi graphs were discovered by Mr. - not surprisingly - Voronoi, over a hundred years ago.

While the Voronoi graph is defined by very simple rules, it usually takes more than one sentence to explain it to someone. Let me try in my own words:

The Voronoi diagram divides the space into cells based on the input set of points. Each point defines one cell. Cell borders are drawn so that they divide the space equidistantly among the points. As a result, each location within a cell has the closest input point in the same cell.

For more info, see the Wikipedia's article on Voronoi.

Or try this interactive presentation (click in diagram to create new points!).

(if you have java installed, you may also try this, this or this)

There's something mesmerizing about Voronoi diagram. It is very similar to the patterns in nature. Soap bubbles, tissue cells...

It's also very appropriate for my "genotype-phenotype" requirements: a simple set of points can define complex spatial forms, which look natural as well.

Mission: Increase Density

While my first experiments with Genetic Algorithms (GA) and floor plan optimization didn't exactly pass with flying colors, I decided to try with simpler problems first.

The most simple problem I could think of, was: each subject is represented with a randomly distributed set of points in space. Fitness funcion: the subjects with more points nearer to the center of the space are more fit.

After running GA several thousand times, the "density" of points was increased as expected. But even then, the local optimum problem stopped the process short of compressing the cloud of points into single point at the center of space (which would give the subject best fitness assessment).

I experimented a lot with different stategies, trying to overcome obstacles in the GA. As the theory suggested, proper mutations are the key weapon in fighting the local optimum problem. I added several "complications" in my mutation system: parametrization and randomization of when, where and how the mutations occur.

The results were improved, however, I must admit that my GA can't achieve the destined goals yet.