Zur Bestimmung der Entfernung zwischen zwei Punkten p und q der Ebene wird üblicherweise die euklidische Abstandsfunktion benutzt.

|pq| := ( (px - qx)2 + (py - qy)2 )1/2

Allgemeiner kann die Distanz von zwei Punkten durch eine konvexe Distanzfunktion dC gemessen werden. Eine konvexe Distanzfunktion kann folgendermaßen definiert werden. Sei C eine kompakte, konvexe Menge in der Ebene, die den Nullpunkt im Innern enthält, dieser wird als das Zentrum bezeichnet. Um den Abstand von p nach q bezüglich C zu definieren, wird C um den Vektor verschoben; siehe Abbildung.

Abb.: Distanzfunktion

Der Strahl von p durch q schneidet den Rand von C in genau einem Punkt q'. Nun definiert man

dC(p,q) := |pq| / |pq'|,

diese Zahl ist genau der Faktor, um den das nach p verschobene C skaliert werden müßte, damit sein Rand den Punkt q enthält. Die Funktion dC erfüllt dC(p,q) >= 0 und dC(p,q) = 0 gilt genau dann, wenn = q ist.  dC erfüllt noch die Dreiecksungleichung

dC(p,r) <= dC(p,q) + dC(q,r).

Die Symmetriebedingung dC(p,q) = dC(q,p) gilt nur, wenn C in bezug auf den Nullpunkt symmetrisch ist; dann ist dC  auch eine Metrik. Eine konvexe Distanzfunktion heißt glatt, falls jeder Punkt auf dem Rand von C nur genau eine Stützgerade besitzt. Eine konvexe Distanzfunktion heißt strikt konvex, falls C keine Liniensegmente (gerade Stücke) im Rand enthält.

Natürlich kann man auch zu konvexen Distanzfunktionen die Bisektoren bestimmen und Voronoi-Diagramme berechnen.

Convex Bisector

Sie sehen in den zwei Fenstern :

Convex Hull: Eine Menge von Punkten und ihre konvexe Hülle. Man kann einen Punkt einfügen (entfernen) durch die linke (rechte) Maustaste,  ein Punkt kann bewegt werden,
dadurch, daß man die linke Maustaste festhält und bewegt. Die konvexe Hülle wird immer neu berechnet, falls ein Punkt eingefügt, entfernt oder bewegt wird. Der dicke Punkt im Inneren der konvexen Hülle ist das sogenannte Zentrum.
 

Bisector: Zwei Punkte in der Ebene und ihr Bisektor bezüglich der konvexen Distanzfunktion, die durch das konvexe Polygon im Convex-Hull-Fenster definiert ist. Das konvexe Polygon wird kopiert und zu den zwei Punkten verschoben, jeder Punkt ist das Zentrum des verschobenen konvexen Polygons. Man kann die zwei konvexen Polygone skalieren, wenn man den Punkt auf der Gerade nach links oder rechts bewegt. Man kann beobachten, daß die beiden "Kreise" sich immer auf dem Bisektor schneiden, und der Bisektor von zwei Punkten aus einer polygonalen Kette mit zwei Strahlen an den Enden besteht. No applet tag recognized.

Convex Voronoi

Das Voronoi-Diagramm einer Menge S von n Punkten in der Ebene ist eine Zerlegung der Ebene in n Regionen, jede Voronoi-Region VR(p,S) für aus S enthält genau die Punkte, die näher zu p als zu irgend einem anderen Punkt in S sind. Wenn als Distanz von zwei Punkten die Länge der geraden Verbindung der Punkte genommen wird, dann haben wir das bekannte Voronoi-Diagramm unter der euklidischen Metrik.

Allgemeiner kann die Distanz von zwei Punkten durch eine konvexe Distanzfunktion dC gemessen werden, wobei C eine kompakte, konvexe Menge in der Ebene ist.

Ein Voronoi-Diagramm unter einer glatten, strikt konvexen Distanzfunktion dC hat ähnliche Eigenschaften wie das unter der euklidischen Metrik. Falls eine konvexe Distanzfunktion nicht strikt konvex ist, dann ist ein Bisektor von zwei Punkten nicht unbedingt eine Kurve, er kann Flächen enthalten. Diese Besonderheit kann nur passieren, falls die Verbindungslinie von zwei Punkten parallel zu einer Kante am Rand von C ist. In diesem Fall enthält der Bisektor eigentlich eine Fläche zwischen zwei zusammenstoßenden Strahlen. Wir können dann vereinbaren, daß als Bisektor nur ein Strahl genommen wird, der in der Fläche liegt. Dadurch ist ein Bisektor unter einer konvexen Distanzfunktion doch immer eine Kurve und das Voronoi-Diagramm ist eine vollständige Zerlegung der Ebene.

In diesem Programm werden Voronoi-Diagramme unter konvexen Distanzfunktionen gezeigt, wobei die konvexen Mengen C Polygone sind. Das Fenster Convex Hull zeigt das konvexe Polygon, und das Fenster Voronoi  zeigt das Voronoi-Diagramm bezüglich des konvexen Polygons. Man kann einen Punkt einfügen (entfernen) durch die linke (rechte) Maustaste, ein Punkt kann bewegt werden, dadurch, daß man die linke Maustaste festhält und bewegt. Die konvexe Hülle und das Voronoi-Diagramm werden immer neu berechnet, falls ein Punkt eingefügt, entfernt oder bewegt wird.  Es ist zu beobachten, daß die topologischen Eigenschaften des Voronoi-Diagramms erhalten bleiben, falls man das Zentrum des Polygons im Convex Hull Fenster innerhalb des Polygons und nicht zu nah zum Rand bewegt. No applet tag recognized.

© 1997 FernUniversität Hagen, Praktische Informatik VI
© 2001 Universität Bonn, Institut für Informatik I

Autor: Lihong.Ma@fernuni-hagen.de