Das Voronoi Spiel

In dieser Diplomarbeit wird das sogenannte Voronoi Spiel betrachtet und analysiert, das man anschaulich folgenderma├čen beschreiben kann:

Das Voronoi Spiel im Kreis:

Es gibt n Personen (durchnummeriert von 1 bis n) zufälligerweise in einem kreisförmigen Raum. Am Anfang kommt der erste Spieler mit Spielnummer 1 an die Reihe, die andere dürfen sich nicht bewegen. Der erste Spieler soll so lange im Raum spazieren, bis er am weitesten entfernt von den anderen Spielern im Raum ankommt, das heisst, der minimale Abstand zu allen anderen Spieler maximiert wird, dann bleibt er stehen und kommt der zweite Spieler an die Reihe. Er muss auch weit wie möglich von den anderen Spielern weggehen. Dann kommt der Dritte, danach der Vierte und so weiter. Nach dem letzten Spieler mit Spielnummer n kommt wieder der erste Spieler an die Reihe und das Spiel wird beliebig lange weitergespielt. Wir möchten gern wissen, wo sich die Spieler nach langer Zeit befinden, falls sich jeder schon beliebig vielmal bewegen durfte.

Punkte im Kreis

Das Voronoi Spiel auf der Kugeloberfläche:

Jetzt sind die n Personen auf einem kugelförmigen Planeten. Sie können nur auf der Oberfläche des Planeten spazieren. Die Spielregeln sind gleich wie im Fall des Kreises: am Anfang haben die Spieler zufällige Positionen, in jedem Schritt kann sich nur ein Spieler (nach Spielnummer) bewegen und er muss die weiteste Stelle auf dem Planeten von den anderen Mitbewohnern finden. Die Frage lautet auch hier so, wo sich die Spieler nach beliebig viele Iterationsschritten auf dem Planeten befinden.

Punkte auf der Kugeloberfläche



Für beide Fälle stellt sich die Frage, ob dieses Verfahren überhaupt gegen eine stabile Konfiguration konvergiert. Die Charakterisierung der stabilen Konfiguration ist auch spannend und im allgemein Fall nichttrivial. Bei der mathematischen Betrachtung des Spieles sind die Spieler durch Punkte innerhalb des Kreises bzw. auf der Kugeloberfläche zu repräsentieren. Die folgenden Applets zeigen, was mit den Punkten im Kreis bzw. auf der Kugeloberfläche passiert.

Der Sinn des Voronoi-Diagramms

Die neue Position des aktuellen beweglichen Punktes (Spieleres) wird mit wenigem Aufwand berechnet, falls man nur die Voronoi-Knoten des Voronoi-Diagramms von den restlichen Punkten (Spieler) und im Falle des Kreises noch die Randpunkte betrachtet. Um zu erfahren, welche zwei Ecken (Punktpaare) auf der Kugeloberfläche miteinander verbunden sein sollen, das Polyeder, eigentlich die konvexe Hülle der Punkte, zu berechnen, kann man Hyperebenetest oder Voronoinachbarschafttest durchführen. Beim letzteren wird die folgende Tatsache ausgenutzt: Zwei Punkte sind genau dann Voronoi-benachbart, dass heisst sie sind mit einer Delauney-Kante in Delauney-Zerlegung verbunden, wenn sie im Polyeder mit einer Kante verbunden sind. Die Voronoinachbarschaft kann man in einer Matrix speichern. Das Polyeder wird dadurch visualisiert, dass man die Voronoi-banachbarte Punkte mit eine Linie verbindet.

Hier ist eine Dokumentation über theoretische und numerische Ergebnisse:

Diplomarbeit          Folien          Projektor