The Program DUST

These images were created at the Institut für Informatik of the Universität zu Köln during summer 1993. They show the visualization capabilities of the program DUST. With this software, one can compute and visualize Voronoï diagrams, Delaunay triangulations, primal and dual spanning trees, and matchings in different metrics.

The next two pictures show Voronoï diagrams, both in L2 metrics. In both pictures the regions are randomly colored.

The following four example pictures show dual spanning trees in L1, L2, L3, and Lmax metrics. The graph is always the same. It contains 70 nodes that are randomly arranged in the plane. Shown are only these nodes (as black dots) and colored "moats" that prove the optimality of the spanning tree (which is not shown).

The moats that surround the nodes can also be regarded discs that are stacked upon the nodes in the three dimensional space. To visualize this, one can produce data to feed a ray shading program. Here comes a minimal spanning tree shown in both ways.

Authors of DUST:

Martin Diehl
Michael Jünger
Volker Kaibel
Thomas Lange
Gerd Reinelt (Universität Heidelberg)

...back to Home Page