 |
|
|
|
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 p verschoben; siehe Abbildung.
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 p = 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.
Autorin: Lihong.Ma@fernuni-hagen.de
© 1997 FernUniversität Hagen, Praktische Informatik VI
© 2001
Universität Bonn, Institut für Informatik I
