 |
|
|
|
|
Das Vornoi-Diagramm mit Airlinemethrik ist eine mögliche Anwendung von Voronoidiagrammen mit additiven Gewichten.
In der Airlinemethrik werden zusätzlich zu den üblichen Punkten, für die das Voronoidiagramm gebildet wird, sog. Flughäfen eingeführt, zwischen denen die Verbindung schneller (oder allgemeiner kostengünstiger) ist, als die Geschwindigkeit, bzw. die Kosten, zwischen zwei üblichen Punkten der Ebene.
Genauer ist die Airlinemethrik wie folgt definiert
:
Sei (X,d) ein metrischer Raum und G=(V,cost) ein positiver, symmetrischer Graph mit
V⊆X. Dann sei wie folgt die Airlinemetrik adG,d:XxX→ℜ+ definiert
:
adG,d(x,y) := min(d(x,y), minv,w∈V(d(x,v) + costG,d(v,w) + d(w,y))
]Sind die Verbindungen zwischen den Flughäfen schnell bzw. kostengünstig genug, so kann es sein, dass ein Gebiet um einen Flughafen nicht zu der Voronoiregion des vom Abstand her nächsten Punktes gehört, in dessen Voronoiregion der Flughäfen üblicherweise liegen würde, sondern zur Voronoiregion eines weiter weg liegenden, aber schneller bzw. günstiger erreichbaren Punktes gehörten. Voronoiregionen müssen in diesem Fall also nicht mehr zusammenhängend sein, sondern können sowohl aus der Region unmittelbar um den zugehörigen Punkt als auch um Gebiete um einen oder mehrere Flughäfen bestehen. In dem folgenden Beispiel sind die einzelnen zur Vornoiregionen für den rot umkringelten Punkt gehörenden Gebiete rot markiert, die Flughäfen und ihre Verbindungen sind in schwarz eingezeichnet.
© 1997 FernUniversität Hagen, Praktische Informatik VI
© 2001
Universität Bonn, Institut für Informatik I
Autor: Oliver Münch
