Was sind Voronoi-Diagramme?
Stelle dir vor, auf einer Karte hast du eine Reihe von Schlössern. In jedem dieser Schlösser lebt ein König. Natürlich kommt es zwischen den Königen immer wieder zum Streit um das umliegende Land. Denn jeder König möchte möglichst viel Land für sich haben. Allerdings sind die Könige auch sehr auf ihren Ruf bedacht, weshalb sie das Land gerne fair aufteilen möchten. Nach einigen Beratungen haben sie folgende einfache Regel vereinbart. Jedes Stück Land soll demjenigen König gehören, dessen Schloss in der geringsten Entfernung zu diesem Stück Land liegt.
Die Grenze zwischen zwei Königreichen ist schnell gefunden, denn so viel weiss auch ein König, diese Grenze lässt sich auf einer Karte mittels der Mittelsenkrechtenkonstruktion einzeichnen. Allerdings wird es schon ein wenig komplizierter, wenn dabei drei oder gar vier Königreiche berücksichtigt werden müssen. Hier kannst du eine Karte herunterladen, auf der einige Königreiche eingezeichnet sind. Schaffst du es, die Grenzen richtig einzuzeichnen?
Tatsächlich wurden die ersten Voronoi-Diagramme von Hand gezeichnet. Ein gutes Beispiel stammt aus René Descartes "Principia Philosophiae" (Grundlagen der Philosophie). Dort macht sich Descartes im 17. Jahrhundert unter anderem Gedanken über die Organisation des Himmels und erklärt, dass es neben der Sonne noch weitere Sterne gäbe. Diese würden wie unsere Sonne von Himmelskörpern umkreist. Wenn nun ein solcher Himmelskörper von einem anderen Stern in unser Sonnenreich gelange, habe dieser eine äussert seltsame Umlaufbahn. Damit hatte Descartes eine Erklärung für das Verhalten von Kometen zur Hand. Seine Gedanken illustrierte er mit einer Grafik, auf der die unterschiedlichen Sterne zu sehen sind.
René Descartes: Principia Philosophiae
Der Name Voronoi-Diagramm geht aber auf den russischen Mathematiker Georgi Feodosjewitsch Woronoi zurück, der sich 1908 mit den mathematischen Eigenschaften solcher Diagramme beschäftigte. Die von ihm und anderen Mathematikern entwickelten Verfahren sind zwar effizienter als das Zeichnen von Mittelsenkrechten und können auch für mehrdimensionale Räume verwendet werden, sie übersteigen aber die Möglichkeiten der Mathematik, wie sie in der Sekundarstufe üblich ist.
Deshalb werden wir, wenn wir solche Diagramme berechnen, auf die ursprüngliche Definition zurückgreifen und jeden Punkt demjenigen "König" zuordnen, welcher am wenigsten weit von diesem Punkt weg ist.