Deutsch English

Centroidal Voronoi Diagrams/Tesselations

The subject Centroidal Voronoi Diagrams/Tesselations was worked out as a diploma thesis at the FernUniversitaet in Hagen/University in Hagen. It was supervised by Dr. Christian Icking and Dr. Lihong Ma, Lehrgebiet Praktische Informatik VI.

Centroidal Voronoi Diagrams

At first Centroidal Voronoi Diagrams are Voronoi Diagrams:

Voronoi Diagrams

The Voronoi Diagram partitions a given space into disjoint regions, the Voronoi regions. Therefore a point set – the Voronoi sites – is given. Each Voronoi site corresponds to one region and any point inside a region is nearer to its Voronoi site than to any other Voronoi site.

The following figure demonstrates this for 256 sites; the crosses are the Voronoi sites, the lines are the regions. Additionally the centroids are marked with circles.

Centroidal Voronoi Diagrams

The Centroidal Voronoi Diagram is a Voronoi Diagram where the Voronoi sites are also the centroids of their regions. As a result of this it has an interesting property: The Centroidal Voronoi Diagram is in some sense optimal.

The following figure shows a Centroidal Voronoi Diagram in a yellow coloured square. You can see that Voronoi sites and centroids are the same. Further on the Voronoi sites are distributed more uniformly in the Centroidal Voronoi Diagram.

More diagrams can be seen in appendix B of the diploma thesis.

Application

Optimisation

Some applications result from the optimisation property of the Centroidal Voronoi Diagram. One of them is described here:

Given the inner city of a town in which post boxes should be placed. Each client uses the next post box. The quality of the distribution depends on the distance between all post boxes and their clients.

The solution of that problem leads to a Centroidal Voronoi Diagram.

Given 256 post boxes, a square as inner city and an uniform population density. Then the first of the above figures could be the post box distribution before the optimisation and the second after it.

Interactive Demo

Java-applet CentroidalVoronoi

By clicking on Start! the Java-applet CentroidalVoronoi will be started. Centroidal Voronoi Diagrams can be constructed interactively.

CentroidalVoronoi is controlled with the buttons in the toolbar. A short description will be shown as tooltip when the mouse is pointing some time to a button.

Plug-ins

It is possible to add further density functions to the applet. A German description can be found in appendix A of the diploma thesis.

An overview of the used Java classes is accessible here.

CentroidalVoronoi can be started offline by downloading the jar-file (approx. 179 kB). The start command is java -jar CentroidalVoronoi.jar.

Diploma thesis

The complete diploma thesis (in German) can be downloaded as pdf-file (approx. 5.4 MB).

Alternatively the whole text can be read online as html-pages. The html-pages are converted with the LaTeX2HTML-Converter. Conversion errors are not corrected.

Source code LaTeX

The LaTeX source code can be obtained from the author.

Source code CentroidalVoronoi

The Java source code can be downloaded as tgz-archive (approx. 94 kB). It is licensed under the conditions of the GNU General Public License, see also the copyright dialog of CentroidalVoronoi.

?

Christian Raskob