Mathematik: Voronoi-Diagramme und Anwendungen
Released by matroid on So. 06. November 2005 17:50:46 [Statistics]
Written by CyberDevil - 7303 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\) In diesem Artikel möchte ich einen kleinen Überblick über Voronoi-Diagramme geben. Ich beschränke mich nicht auf das in Vorlesungen übliche klassische Voronoi-Diagramm, sondern erläutere auch das Voronoi-Diagramm von Liniensegmenten. Desweiteren gehe ich auf einige Anwendungen in der Informatik ein. Beispiel Voronoi-Diagramm und Minkowski-SummeAufgrund der Komplexität der Thematik gebe ich nur einen Überblick und werde auf Beweise verzichten. Ich habe mich bemüht, mit vielen Skizzen zum Verständnis beizutragen und die Thematik aufzulockern. Zudem habe ich Links im Artikel angegeben, mit denen man zu Applets gelangt, um sich experimentell mit der Thematik vertraut zu machen.
Hier zunächst eine Übersicht über die einzelnen Abschnitte: 1. Das allgemeine Voronoi-Diagramm 2. Das Voronoi-Diagramm von Punkten 3. Anwendungen des Voronoi-Diagramms von Punkten 4. Das Voronoi-Diagramm von Liniensegmenten 4.1. Bisektoren 4.2. Voronoi-Regionen 4.3. Voronoi-Diagramm 5. Anwendungen des Voronoi-Diagramms von Liniensegmenten 6. Links und Literatur

1. Das allgemeine Voronoi-Diagramm Voronoi-Diagramme sind – im weitesten Sinne – bei der Analyse von Distanz- Problemen hilfreich. Dadurch ergeben sich vielfältige Einsatz-Möglichkeiten in der Praxis, beispielsweise bei der Bewegungsplanung oder bei der Erkennung von Schrift. Daher bilden sie ein umfassendes Gebiet der Algorithmischen Geometrie, auf dem auch weiterhin intensiv geforscht wird. Auf konkrete Anwendungen gehe ich später ein. Das Voronoi-Diagramm wurde nach dem russischen Mathematiker Gregory Voronoi benannt. Teilweise wird es auch Dirichlet tessellation genannt. makro(stress,\stress\ %1\normal) Allgemein betrachtet man eine Menge \calS von Objekten in einem Raum \IK^n. Das stress(Voronoi\-Diagramm) VD(\calS) bildet eine Zerlegung des Raumes \IK^n in stress(Voronoi\-Regionen) VR(p) für p \in \calS. Die Voronoi\-Region VR(p) beinhaltet genau die Punkte des Raumes \IK^n, die zu p eine geringere Distanz haben, als zu den anderen Objekten p'\in\calS\\ {p}. Je nach Wahl des Raumes \IK^n, der Distanz\-Definition und der Objektmenge \calS erhält man unterschiedliche Voronoi\-Diagramme. Betrachtet man Objekte in metrischen Räumen, so wird bereits durch die Metrik eine Distanz definiert. In diesem Artikel wird nur der Fall \IK = \IR und n=2 betrachtet.
2. Das Voronoi-Diagramm von Punkten Man bezeichnet dieses Voronoi\-Diagramm auch als klassisches Voronoi\-Diagramm und versteht darunter das Voronoi\-Diagramm einer endlichen Punktmenge unter der euklidischen Metrik im \IR^2. Ich gebe nun kurz die wesentlichen Definitionen und Eigenschaften an. Sei \calS := {p_1 ,..., p_n} eine nichtleere, endliche Menge von paarweise verschiedenen Punkten p_i\in\IR^2. Für einen beliebigen Punkt \xi\in\IR^2 definiert man den Abstand von \xi zu \calS durch d(\xi,\calS) := \min {d(\xi,p) : p\in\calS }. Für p, q\in\calS definiert man folgende Mengen: (1) B(p,q) := {\xi\in\IR^2 : d(p,\xi) = d(q,\xi)} heißt der\red Bisektor von p und q. (2) VR(p,\calS) := {\xi\in\IR^2 : \forall q\in\calS\\{p} : d(p,\xi) < d(q,\xi)} heißt die\red Voronoi\-Region von p bezüglich \calS. (3) VD(S) := \IR^2 \\ union(VR(p,\calS),p\in\calS,) heißt das\red Voronoi\-Diagramm von \calS. Ich möchte kurz die Form des Voronoi\-Diagramms und der involvierten Begriffe veranschaulichen: (1) Der Bisektor zwischen zwei Punkten ist eine Gerade, nämlich die Mittelsenkrechte der Punkte. (2) Die Voronoi\-Region VR(p,\calS) des Punktes p besteht aus genau den Punkten der Ebene \IR^2, die zu p näher liegen als zu allen anderen Punkten aus \calS. (3) Jeder Punkt z\in VD(\calS) des Voronoi\-Diagramms hat zu mindestens zwei Punkten aus \calS den gleichen minimalen Abstand d(z,\calS). Man kann das Voronoi\-Diagramm auch über die Ränder der Voronoi\-Regionen definieren, da VD(\calS) = union(\partial VR(p,\calS),p\in\calS,) gilt. Hier eine Skizze zu einem Voronoi\-Diagramm zu fünf Punkten. Die Punkte sind rot dargestellt, das Voronoi\-Diagramm blau. Es ist eine beschränkte Voronoi\-Region in der Mitte zu sehen und vier unbeschränkte Voronoi\-Regionen, die an die beschränkte Voronoi\-Region angrenzen.
Voronoi-Diagramm
Es gibt einen interessanten Bezug vom Voronoi\-Diagramm zur konvexen Hülle der Punkte. Bezeichne ch(\calS) die konvexe Hülle der Punkte von \calS. Für die Voronoi\-Region eines Punktes p\in\calS gelten folgende zwei Aussagen: (a) VR(p,\calS) ist konvex. (b) VR(p,\calS) unbeschränkt <=> p\in \partial ch(\calS). Beim Voronoi\-Diagramm von Liniensegmenten wird man sehen, dass Voronoi\-Regionen i.a. nicht konvex sind, d.h. (a) gilt nicht für jegliche Arten von Voronoi\-Diagrammen. Die interessantere Aussage ist jedoch (b). Mittels dieser Aussage lässt sich aus dem Voronoi\-Diagramm von Punkten die konvexe Hülle konstruieren, indem man alle unbeschränkten Voronoi\-Regionen im mathematisch positiven Umlaufsinn abläuft und so alle Punkte aus dem Rand der konvexen Hülle im mathematisch positiven Umlaufsinn erhält. Da die Berechnung der konvexen Hülle eine Laufzeit aus O(n \log n) benötigt, benötigt somit insbesondere die Berechnung des Voronoi\-Diagramms eine Laufzeit auf \Omega(n \log n). Es gibt jedoch veschiedene Verfahren, die in optimaler Laufzeit aus O(n \log n) das Voronoi\-Diagramm zu n Punkten bestimmen, z.B. divide-and-conquer-Verfahren oder Plane-Sweep-Verfahren (draufklicken für Details). Ein Applet, um mal mit Voronoi-Diagrammen von Punkten zu experimentieren, findet sich hier. Auf www.voronoigame.com findet sich ein interessantes Spiel basierend auf Voronoi-Diagrammen von Punkten. Das Voronoi\-Diagramm besteht aus Knoten und Kanten. Die Knoten sind Punkte, die zu mindestens drei Elementen aus \calS den gleichen Abstand haben. Eine Kante des Voronoi\-Diagramms ist der Schnitt des Voronoi\-Diagramms mit einem Bisektor zweier Punkte aus \calS. Da der Bisektor eine Gerade ist, ist eine Kante des Diagramms ein Liniensegment oder eine Halbgerade. Der oder die Endpunkte sind dann Knoten des Voronoi\-Diagramms. Die Anzahl der Knoten ist endlich. Man kann einen Kreis \Gamma ziehen, der alle Knoten des Voronoi\-Diagramms und alle Punkte aus \calS enthält. Dieser Kreis kreuzt nur die unbeschränkten Kanten. Entfernt man außerhalb von \Gamma die Kanten, so erhält man das so genannte\red beschränkte Voronoi\-Diagramm\black BV(\calS). Dieses beschränkte Voronoi\-Diagramm bildet einen kreuzungsfreien geometrischen Graphen. Betrachtet man das Voronoi\-Diagramm als Graphen, so kann man dann leicht zeigen: (a) VD(\calS) hat O(n) Knoten und Kanten, (b) Der Rand einer Voronoi\-Region VR(p,\calS), p\in\calS besteht im Mittel aus höchstens sechs Kanten. (c) Liegen die Punkte der Menge \calS nicht alle auf einer Geraden, so ist das Voronoi\-Diagramm zusammenhängend. Aufgrund der Konvexität haben die Ränder zweier Voronoi\-Regionen höchstens eine Kante des Voronoi\-Diagramms gemeinsam. Zwei Regionen heißen benachbart, wenn eine solche Kante existiert.
3. Anwendungen des Voronoi-Diagramms von Punkten Mittels des Voronoi\-Diagramms von Punkten können viele verschiendene Aufgaben effizient erledigt werden. Im folgenden nenne ich einige Beispiele: (a) Bestimmung des nächsten unter n Postämtern. Bei diesem Problem geht es darum, zu gegebenem Punkt x in möglichst kurzer Zeit das nächste Postamt zu ermitteln. Es kann in linearer Zeit und mit linearem Speicherbedarf eine Struktur aus dem Voronoi\-Diagramm hergestellt werden, so dass sich obige Anfrage nach dem nächsten Postamt in O(\log n) Zeit beantworten lässt. Es muss jedoch berücksichtigt werden, dass die (einmalige) Berechnung des Voronoi\-Diagramms O(n \log n) Zeit benötigt. (b) Bestimmung aller nächsten Nachbarn. In linearer Zeit können für alle Punkte, zu denen das Voronoi\-Diagramm bestimmt wurde, die jeweils nächsten Nachbarn durch Ablaufen aller Voronoi\-Regionen bestimmt werden. Denn jeder nächste Nachbar eines Punktes x sitzt im Voronoi\-Diagramm in einer Voronoi\-Region, die mit VR(x) eine gemeinsame Kante hat. Somit kann auch das dichteste Paar von Punkten in linearer Zeit bestimmt werden. Auch hier muss berücksichtigt werden, dass die (einmalige) Berechnung des Voronoi\-Diagramms O(n \log n) Zeit benötigt. (c) Bestimmung eines minimal spannenden Baumes. Man erstellt zunächst einen Graphen zu den Punkten p_1 ,..., p_n , indem man zu jedem Punkt p_i einen Knoten erstellt und jeden Knoten mit jedem anderen über eine Kante verbindet. Dann ermittelt man mit dem Verfahren von Kruskal einen minimal spannenden Baum. Der Algorithmus von Kruskal benötigt dafür eine Zeit von O(n^2 \log n). Mit Hilfe des Voronoi\-Diagramms zu den Punkten p_1 ,..., p_n kann man diese Laufzeit verbessern. Denn man kann zeigen, dass im Algorithmus von Kruskal nur Kanten betrachtet werden müssen, deren Endpunkte in benachbarten Voronoi\-Regionen liegen. Dadurch erhält man eine Laufzeit von O(n \log n) für die Bestimmung eines minimal spannenden Baumes. (d) Bestimmung des größten leeren Kreises. Ist A ein konvexes Polygon mit m Kanten bzw. Ecken, so kann mit Hilfe des Voronoi\-Diagramms der Kreis mit größtem Radius und Mittelpunkt innerhalb von A, der keine Punkte aus \calS enthält, in einer Zeit von O(m \log n + n) bestimmt werden. Details zu (d) werden hier ab S. 42 gegeben. Man sieht also, dass das Voronoi-Diagramm eine Vielzahl von Anwendungen hat und sich dadurch elegant Verbesserungen von "naiven" Verfahren erreichen lassen.
4. Das Voronoi-Diagramm von Liniensegmenten Gegeben sei nun eine endliche Menge \calS von Liniensegmenten in der reellen Zahlenebene \IR^2. Bezugnehmend auf die Anwendungen des Voronoi\-Diagramms von Punkten könnte man sagen, man betrachtet nun liniensegmentförmige Postämter. Im folgenden wird also die Struktur des Voronoi\-Diagramms zu solchen Liniensegmenten unter der euklidischen Metrik untersucht. Hierbei kann ein Punkt als Spezialfall eines Liniensegments aufgefasst werden. Zunächst wird der Bisektor von Liniensegmenten betrachtet.
4.1. Bisektoren Die Menge B(k,l) := {p\in\IR^2 : d(p,k) = d(p,l)} heißt \red Bisektor\black der Liniensegmente k und l bezüglich der euklidischen Metrik. Der Bisektor beinhaltet alle die Punkte des Raumes, die zu beiden Objekten den gleichen Abstand haben. Für zwei verschiedene Punkte ist diese Menge gerade die Mittelsenkrechte der Punkte; für zwei sich schneidende Geraden besteht der Bisektor aus den beiden Winkelhalbierenden. Für Liniensegmente genügt eine solche Beschreibung nicht. Daher beschreiben wir nun den Verlauf des Bisektors für alle auftretenden Kombinationen. Zu zwei Liniensegmenten k und l kann dieser z.B. wie folgt aussehen:
Bisektor zweier Liniensegmente
(a) Punkt-Punkt-Bisektor: es handelt sich offensichtlich um die Mittelsenkrechte der beiden Punkte. (b) Punkt-Liniensegment-Bisektor: Sei l = ab^- \subset\IR^2 ein Liniensegment und g die Gerade mit l \subset g. Zunächst benötigt man zur Analyse der Bisektoren die\red Streifenzerlegung\black von \IR^2 bezüglich des Liniensegmentes l. Sei x ein Punkt in \IR^2 und y\in l der Punkt von l, der kürzesten Abstand von x hat. Ist xl^- das Lot auf l, so sagt man "x liegt im Streifen von l". Man schreibt dafür x\in S(l). Ansonsten gilt entweder y=a oder y=b. H_a (l) enthalte die Punkte x, für die y=a gilt und H_b (l) entsprechend die Punkte, für die y=b gilt. Wir bezeichnen H_a (l) und H_b (l) als Halbebenen zu l.
Bild
Gilt p\notel g, dann ist der Bisektor B(p,l) eine Kurve, die aus einem Parabelsegment und zwei Halbgeraden besteht. Das Parabelstück hat den Brennpunkt p, die Leitlinie g und verläuft in dem Streifen S(l). Denn die Punkte auf einer Parabel sind gerade die Punkte, die gleichen Abstand vom Brennpunkt und der Leitlinie haben. Außerhalb des Streifens bilden die Mittelsenkrechten der Endpunkte a und b von l mit dem Punkt p den Bisektor.
Bisektorstück ist Parabel
Gilt p\in g, dann ist der Bisektor a) für p\in l\\{a,b}: die Senkrechte auf l durch p. b) für p\in {a, b}: die Halbebene H_a (l) bzw. H_b (l). c) für p\in g \\ l: die Mittelsenkrechte zwischen p und dem nächstgelegenen Endpunkt von l. Besteht das Liniensegment l nur aus einem Punkt, so ist der Bisektor die Mittelsenkrechte zwischen p und l. Man kann diesen Fall so interpretieren, dass das Parabelstück des Bisektors nur aus dem Mittelpunkt zwischen p und l besteht. Nur im Sonderfall b) ist der Bisektor keine Kurve. Diesen Fall schließt man daher aus. (c) Bisektor disjunkter Liniensegmente: Man kann zeigen, dass der Bisektor auch in diesem Fall eine Kurve ist, die aus maximal sieben Teilstücken besteht. Dazu betrachtet man den Verlauf des Bisektors auf dem Schnitt der Streifen, dem Schnitt von Streifen und Halbebenen und dem Schnitt von Halbebenen von l und k. Auf den einzelnen Schnitten ergibt sich der jeweilige Teil des Bisektors dann als Punkt-Punkt-, Punkt-Liniensegment oder Liniensegment-Liniensegment-Bisektor, wie die folgenden Skizzen illustrieren. Die folgende Skizze zeigt den Bisektor im Schnitt der Streifen:
Bisektor im Schnitt der Streifen
Die folgende Skizze zeigt den Bisektor im Schnitt von Streifen und Halbebene:
Bisektor im Schnitt von Streifen und Halbebene
Die folgende Skizze zeigt den Bisektor im Schnitt der Halbebenen:
Bisektor im Schnitt der Halbebenen
Bei anderer Lage der Liniensegmente sind ggfs. andere Schnitte von Streifen bzw. Halbebenen zu betrachten. Die obigen Aussagen verlieren dadurch jedoch nicht ihre Gültigkeit. Ein Bespiel dafür stellt die folgende Skizze dar, die einen Bisektor aus sieben Teilstücken darstellt:
Bisektor aus sieben Teilstücken
Es bleibt noch zu erwähnen, dass aufgrund der Stetigkeit des Abstandsbegriffs ein Bisektorstück beim Verlassen eines Schnittes und Eintritt in einen anderen Schnittbereich stetig fortgesetzt wird, d.h. der Bisektor eine Kurve bildet. (d) Bisektor nicht-disjunkter Liniensegmente: Im vorherigen Abschnitt wurden die Liniensegmente als disjunkt vorausgesetzt und gezeigt, dass der Bisektor dann eine Kurve ist. Diese schöne Eigenschaft bewirkt, dass das aus Teilen von Bisektoren zusammengesetzte Voronoi\-Diagramm von disjunkten Liniensegmenten als geometrischer Graph dargestellt werden kann, was für die algorithmische Berechnung eine erhebliche Erleichterung ist. Wie bereits im Fall von Punkt und Liniensegment gesehen, nämlich falls der Punkt ein Endpunkt des Liniensegments ist, kann auch hier der Bisektor von Liniensegmenten mit gemeinsamen Endpunkten eine Fläche sein. Die entsprechenden Sonderfälle werden in diesem Abschnitt behandelt. Diese Fälle sind nicht unwesentlich, da sich z.B. bei Polygonen aufeinanderfolgende Liniensegmente an ihren Endpunkten berühren. Die möglichen Strategien zur Handhabung solcher Flächen besprechen wir im Anschluss an die Beschreibung der vier Fälle. Bezeichne im folgenden l^o das Liniensegment l ohne seine Endpunkte. (1) Seien k, l zwei Liniensegmente mit {z} = k^o \cap l^o, d.h. k und l schneiden sich echt. Dann besteht der Bisektor B(k,l) aus zwei Kurven, die sich in z berühren. Jede dieser Kurven besteht aus maximal fünf Teilstücken, nämlich - einer Winkelhalbierende durch z auf S(k)\cap S(l), - bis zu zwei Parabelstücken, die aus den entsprechenden Bisektoren zwischen Endpunkt und Liniensegment resultieren, - zwei Halbgeraden als Bisektoren der Endpunkte.
Bisektor sich schneidender Liniensegmente
Fällt die Winkelhalbierende mit der Mittelsenkrechten der zugehörigen Endpunkte zusammen, tritt gar kein Parabelstück auf, da der Schnitt von Streifen und Halbebene leer ist.
Bisektor sich schneidender Liniensegmente ohne Parabelstücke
(2) Der Endpunkt eines Segments liegt auf dem anderen Segment: Bezeichne nun l = ab^-. Ferne gelte {a} = l \cap k^o, d.h. das Liniensegment l liegt mit einem Endpunkt im Innern des Liniensegments k. k und l schließen zwei Winkel ein. Die Winkelhalbierenden bilden auf dem Schnitt der Streifen der Segmente wiederum die Bisektoren, die außerhalb dieses Schnittbereiches wie im vorherigen Fall durch Halbgeraden und ggfs. Parabelstücke fortgesetzt werden. Speziell zu betrachten ist die Halbgerade, die in a senkrecht auf k steht und in der anderen Halbebene von k wie l liegt. Dieser Halbgerade h ist Teil des Bisektors von k und l, da die Punkte von h den Punkt a als Fußpunkt auf k haben, d.h. gleichen Abstand zu k und l haben.
Endpunkt auf anderem Liniensegment
(3) Seien k = ab^- und l = ac^- zwei Liniensegmente mit {a} = l\cap k, d.h. gemeinsamem Endpunkt. Ferner schließen wir zunächst aus, dass l und k auf einer Geraden liegen. Seien weiter (L_a (l), S(l), L_c (l)) und (K_a (k), S(k),K_b (k)) die zugehörigen Streifenzerlegungen. Dann besteht der Bisektor der Liniensegmente k und l aus einer Kurve und einer Fläche. Die Kurve beginnt in a und verläuft durch (S(k) \cup K_b (k)) \cap (S(l) \cup L_c (l)), die Bisektorfläche ist K_a (k) \cap L_a (l). Im Sonderfall, dass k und l auf einer Geraden liegen, ist der Bisektor die Senkrechte durch den gemeinsamen Punkt a, also der Schnitt der Halbebenen K_a (k) und L_a (l).
Liniensegmente haben gemeinsamen Endpunkt
(4) Die Liniensegmente haben ein gemeinsames Teilsegment: Überlagern sich zwei Liniensegmente k und l, so bildet ihr Schnitt ein Liniensegment s, das durch zwei Endpunkte der Segmente definiert wird. Das Schnittsegment s kann sogar mit k oder l übereinstimmen, falls k \subset l oder l \subset k gilt. Alle Punkte innerhalb des zu s gehörigen Streifens S(s) sind gleichweit von k und l entfernt, d.h. der Bisektor in S(s) ist die Fläche S(s) selbst. Im Fall k \subset l oder l \subset k, wobei k und l einen gemeinsamen Endpunkt a haben, gehört sogar die Halbebene der Streifenzerlegung, die a enthält, mit zum Bisektor. In der folgenden Skizze wurden die Ausdehnungen der einzelnen Segmente gesondert kenntlich gemacht, da sie sonst aufgrund der Überlagerung nicht sichbar gewesen wären.
Bisektor sich überlagernder Liniensegmente

4.2. Voronoi-Regionen Die Voronoi\-Region eines Liniensegments s bzgl. der euklidischen Metrik ist die Menge VR(s, S) = VR(s) = {z\in\IR^2 : \forall s_i \in \calS\\{s} gilt d(z,s) < d(z,s_i)}. Der Rand einer Voronoi\-Region besteht also offensichtlich aus Teilen von Bisektoren. Diese Definition macht es i.a. unmöglich, den Rand einer Voronoi\-Region durch einen Graphen darzustellen, da - wie zuvor gesehen - auch Bisektorflächen auftreten können. Daher betrachtet man ein Liniensegment fortan nicht mehr einschließlich seiner Endpunkte, sondern ordnet den Endpunkten eigene Voronoi\-Regionen zu. Schließt man Überlagerungen von Liniensegmenten aus, so unterbindet man durch diese Festlegung das Auftreten von Bisektorflächen, wie man sich direkt anhand der obigen Überlegungen klarmacht. Man bezeichnet dieses Vorgehen als\red Auflösung der Bisektorflächen\black . Wir definieren also die Voronoi\-Regionen zu einem Liniensegment s=ab^- wie folgt: VR(s^o) = {z\in\IR^2 : \forall 1 \le i \le n s_i = (a_i b_i)^- gilt d(z,s^o) < d(z,s_i^o) für s_i != s \and d(z,s^o) < d(z, a_i) \and d(z,s^o) < d(z, b_i)}. Die Voronoi\-Region von p\in{a, b} ist die Menge VR(p) = {z\in\IR^2 : \forall 1 \le i \le n, s_i = (a_i b_i)^- gilt d(z,p) < d(z,s_i^o) \and d(z,p) < d(z,a_i) für a_i != p \and d(z,s^o) < d(z, b_i) für b_i != p}. Auf diese Weise erhält man, sofern die Liniensegmente aus \calS sich nicht schneiden oder im Innern berühren, zusammenhängende Voronoi\-Regionen für alle offenen Liniensegemte aus \calS und ihre Endpunkte. Insbesondere gilt dies für ein Polygon, da sich dort die Liniensegmente nur an ihren Endpunkten berühren. Voronoi\-Regionen sind nach Definition offene Menge und paarweise disjunkt. Allerdings sind Voronoi\-Regionen hier i.a. nicht konvex. Das liegt daran, dass Parabelsegmente im Rand von Voronoi\-Regionen vorkommen, wie wir bei der Beschreibung der Bisektoren gesehen haben. Analog zum Fall der Voronoi\-Regionen des Voronoi\-Diagramms von Punkten kann man auch hier eine Beziehung zur konvexen Hülle herstellen. Die Formulierung ist etwas technischer. Es ist jedoch festzuhalten, dass sich anhand dieses Zusammenhangs eine untere Laufzeitschranke für die Berechnung des Voronoi\-Diagramms eines Polygons mit n Kanten von O(n \log n) ergibt.
4.3. Voronoi-Diagramm Man definiert nach Auflösung der Bisektorflächen das Voronoi\-Diagramm von \calS durch VD(S) := \IR^2 \\ ((union(VR(p,\calS),p Endpunkt von s\in\calS,)) \cup (union(VR(s^o,\calS),s\in\calS,))). Da der Rand einer Voronoi\-Region aus Teilen von Bisektoren besteht, besteht also auch das Voronoi\-Diagramm aus Teilen von Bisektoren. Eine Experimentierumgebung zum Voronoi-Diagramm von Liniensegmenten findet sich hier. Es bietet sich an dieser Stelle an, einmal ein wenig damit zu basteln, um ein "Gefühl" für diese doch etwas komplexere Struktur zu erhalten. Es ist alles andere als einfach, das Voronoi\-Diagramm von Liniensegmenten zu berechnen. Es gibt zwar inzwischen viele Verfahren, die dieses für bis auf an den Endpunkten disjunkte Liniensegmente in O(n \log n) Zeit bestimmen können (z.B. die Verfahren von Kirkpatrick und Yap), jedoch gibt es basierend darauf keine stabile Implementierung. Allerdings haben Held und Karavelas unabhängig voneinander zwei komplett verschiedene Verfahren zur Berechnung des Voronoi\-Diagramms von Liniensegmenten angegeben, die auch in der Praxis stabil laufen. Diese Verfahren schränken die Eingabe\-Menge nicht ein, d.h. akzeptieren auch Segmente, die sich schneiden. Held hat allerdings nur eine experimentelle Laufzeit von O(n \log n) angegeben, während Karavelas eine theoretische Laufzeit von O((n+m)\log^2 n) angibt, wobei m die Anzahl der Schnitte der Liniensegmente bezeichnet. Somit gibt es in dieser Hinsicht weiterhin Verbesserungsspielraum. Betrachtet man ein einfaches Polygon, so kann man dazu ebenfalls das Voronoi\-Diagramm von Liniensegmenten bestimmen. Wie bereits erwähnt, kann man das komplette Voronoi\-Diagramm \(insbesondere den Teil außerhalb des Polygons) nicht schneller als in O(n \log n) Zeit bestimmen. Schränkt man das Voronoi-Diagramm jedoch auf das Innere des Polygons ein, so gelingt dies mit dem Algorithmus von Chin in linearer Zeit. Dieser Algorithmus gilt jedoch als nicht implementierbar. Über gewisse Modifikationen soll dieses Verfahren implementierbar sein; es verliert dadurch jedoch seine Optimalität. Durch diese Modifikationen hat es nämlich eine Laufzeit aus O(n \log^* n). Der iterierte Logarithmus log^* ist eine sehr langsam wachsende Funktion, die für Eingaben aus der Praxis \le 5 bleibt. Somit ist der Verlust der Optimalität akzeptierbar, da in der Praxis das Verfahren dennoch effizient arbeitet. Jedoch gibt es bisher keine solche Implementierung, die nachweist, dass diese Modifikationen tatsächlich zu einem stabilen Algorithmus führen. Auch hier ist also noch Forschungsarbeit zu leisten.
5. Anwendungen des Voronoi-Diagramms von Liniensegmenten Aufgrund ihrer Definition über Abstände finden Voronoi-Diagramme in unzähligen Bereichen Anwendung. Ich nenne hier nur drei grundlegend verschiedene, um das breite Anwendungsspektrum zu verdeutlichen. In der Robotik lassen sich mit ihrer Hilfe kollisionsfreie Wege für einen (je nach Metrik) kreisförmigen Roboter bzgl. polygonaler Hindernisse ermitteln. Dazu prüft man, ob der Roboter entlang eines Weges im Voronoi-Diagramm vom Startpunkt zum Zielpunkt gelangen kann. Man kann zeigen, dass kein kollisionsfreier Weg existiert, wenn nicht ein kollisionsfreier Weg entlang des Voronoi-Diagramms existiert. Desweiteren kann man Voronoi-Diagramme zur Erkennung von Handschrift einsetzen. Ein Paper dazu findet sich hier. Ferner können Voronoi-Diagramme in Geo-Informations-Systemen eingesetzt werden, um Unsicherheitsbereiche zu modellieren. Mit ihrer Hilfe können z.B. polygonale Objekte effizient um eine Puffer-Zone "aufgedickt" werden, wie die nachfolgenden Abbildungen veranschaulichen. Formal handelt es sich bei der Aufdickung um die Minkowski-Summe der gezeigten Polygone mit einem Kreis.
Aufdickung eines Polygons
Aufdickung zweier Polygone
Man erkennt an den Abbildungen, dass die Kreisbögen und Liniensegmente der Aufdickung jeweils auf Kanten des Voronoi-Diagramms enden bzw. beginnen. Dadurch kann ein effizienter Algorithmus zur Konstruktion dieser Puffer-Bereiche angegeben werden.
6. Links und Literatur Wie ich eingangs schon sagte, sind Voronoi-Diagramme ein viel umforschtes Gebiet der Algorithmischen Geometrie. Daher gibt es dazu auch viele Websites und Literatur. Von Aurenhammer und Klein stammt ein Artikel aus dem Handbook of Computational Geometry. Er gibt einen grundlegenden Überblick über die wichtigsten Arten von Voronoi-Diagrammen. Die Abschnitte dieses Artikels zur Theorie der Voronoi-Diagramme von Punkten und Liniensegmenten habe ich auf Grundlage der Arbeit von Schumann zusammengetragen und ggfs. ergänzt. Die Website www.voronoi.com trägt viele Grundlagen und auch weiterführende Erkenntnisse auf dem Gebiet der Voronoi-Theorie zusammen. Die Fernuni Hagen hat eine interessante Website mit einem Geometrie-Labor.
Ich hoffe, ich konnte trotz der Kürze einige Grundlagen zu Voronoi-Diagrammen und ihren Anwendungen vermitteln und vielleicht auch ein wenig Neugier bzgl. dieser überaus nützlichen und interessanten Struktur wecken. Ich möchte noch Matroid herzlich für seine Hilfe mit dem Artikel-System und generell für das tolle System des Matheplaneten danken. Euer CyberDevil
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Informatik :: Geometrie :: Algorithmen :
Voronoi-Diagramme und Anwendungen [von CyberDevil]  
In diesem Artikel möchte ich einen kleinen Überblick über Voronoi-Diagramme geben. Ich beschränke mich nicht auf das in Vorlesungen übliche klassische Voronoi-Diagramm, sondern erläutere auch das Voronoi-Diagramm von Liniensegmenten. Desweiteren gehe ich auf einige Anwendungen in der Informatik ein.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 7303
 
Aufrufstatistik des Artikels
Insgesamt 1035 externe Seitenaufrufe zwischen 2012.01 und 2021.10 [Anzeigen]
DomainAnzahlProz
https://google.de24123.3%23.3 %
https://google.com242.3%2.3 %
https://www.ecosia.org191.8%1.8 %
http://google.de60758.6%58.6 %
https://duckduckgo.com262.5%2.5 %
http://google.fr424.1%4.1 %
https://www.bing.com252.4%2.4 %
http://google.hr161.5%1.5 %
http://www.bing.com161.5%1.5 %
http://google.es20.2%0.2 %
http://images.google.de20.2%0.2 %
http://r.duckduckgo.com20.2%0.2 %
http://google.nl20.2%0.2 %
https://www.startpage.com20.2%0.2 %
https://swisscows.com10.1%0.1 %
http://10.49.0.91:1587110.1%0.1 %
https://html.duckduckgo.com10.1%0.1 %
http://isearch.babylon.com10.1%0.1 %
http://54.65.210.2510.1%0.1 %
http://google.ch10.1%0.1 %
http://avira.search.ask.com10.1%0.1 %
http://google.at10.1%0.1 %
http://ecosia.org10.1%0.1 %

Häufige Aufrufer in früheren Monaten
Insgesamt 988 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2021 (234x)https://google.de/
2012-2018 (223x)http://google.de/url?sa=t&rct=j&q=
2012-2014 (39x)http://google.de/url?sa=t&rct=j&q=voronoi diagramm
2012-2013 (39x)http://google.de/url?sa=t&rct=j&q=voronoi-diagramme
201201-01 (34x)http://google.de/url?sa=t&rct=j&q=voronoi-diagramm
201204-04 (30x)http://google.de/url?sa=t&rct=j&q=voronoi diagramme
2020-2021 (26x)https://duckduckgo.com/
201303-03 (24x)http://google.de/url?sa=t&rct=j&q=voronoi diagramm berechnung free
201207-07 (23x)http://google.de/url?sa=t&rct=j&q=minkowsi bisektor
201304-04 (22x)http://google.de/url?sa=t&rct=j&q=voronoi diagramme anwendungsbeispiele
201211-11 (21x)http://google.fr/imgres?q=diagramme de voronoi
201206-06 (21x)http://google.fr/imgres?q=Minkowski kurve
201203-03 (20x)http://google.de/url?sa=t&rct=j&q=warum voronoi-diagramm
201210-10 (20x)http://google.de/url?sa=t&rct=j&q=Voronoi-Diagramm, Verwendungen
201302-02 (19x)http://google.de/url?sa=t&rct=j&q=voronoy diagramm
2020-2021 (18x)https://google.com/
201306-06 (18x)http://google.de/url?sa=t&rct=j&q=voronoi held
201407-07 (18x)http://google.de/url?sa=t&source=web&cd=2&ved=0CCcQFjAB
2020-2021 (18x)https://www.ecosia.org/
2020-2021 (17x)https://www.bing.com/
201205-05 (16x)http://google.hr/imgres?q=konvexe huelle
201401-01 (15x)http://google.de/url?sa=t&rct=j&q=Formel Voronoi Diagramm
201307-07 (15x)http://google.de/url?sa=t&rct=j&q=voronoi diagram konvexe hülle
201308-08 (12x)http://google.de/url?sa=t&rct=j&q=anwendung voronoi
201212-12 (9x)http://google.de/url?sa=t&rct=j&q=voronoi-diagramm mathe
201411-11 (7x)http://google.de/url?sa=t&rct=j&q=voronoi konstruieren
202107-07 (6x)https://google.de
201505-05 (6x)http://google.de/url?sa=t&rct=j&q=beweis voronoi diagramm konvex
202007-07 (5x)https://www.bing.com/search?q=voronoi diagramm
201511-11 (5x)http://google.de/url?sa=t&source=web&cd=10&rct=j&q=voronoi diagramm zeichnen
201711-11 (4x)http://google.de/url?sa=i&rct=j&q=
201305-06 (4x)http://www.bing.com/search?setmkt=de-AT&q=voronoi diagramm 2 offene halbebene...

[Top of page]

"Mathematik: Voronoi-Diagramme und Anwendungen" | 5 Comments
The authors of the comments are responsible for the content.

Re: Voronoi-Diagramme und Anwendungen
von: Ex_Mitglied_40174 am: So. 06. November 2005 20:54:02
\(\begingroup\)Hallo CyberDevil, ein sehr ästhetisches Thema! Dankeschön! Viele Grüße abc\(\endgroup\)
 

Re: Voronoi-Diagramme und Anwendungen
von: FlorianM am: Fr. 11. November 2005 18:32:30
\(\begingroup\)"Ich hoffe, ich konnte trotz der Kürze einige Grundlagen zu Voronoi-Diagrammen und ihren Anwendungen vermitteln und vielleicht auch ein wenig Neugier bzgl. dieser überaus nützlichen und interessanten Struktur wecken." Das hast du... :) Super erster Artikel von dir. Freue mich auf weitere... 😄\(\endgroup\)
 

Re: Voronoi-Diagramme und Anwendungen
von: CyberDevil am: Sa. 12. November 2005 11:17:23
\(\begingroup\)Freut mich :) Viele Grüße, CyberDevil \(\endgroup\)
 

Re: Voronoi-Diagramme und Anwendungen
von: Kiddycat am: So. 11. April 2010 12:34:28
\(\begingroup\)Hallo, vielen Dank für die kurze Übersicht :) Ich hätte gern noch nachgelesen, was du zur Bestimmung des größten leeren Kreises verlinkt hast, aber der Link führt leider ins Leere. Vielleicht kannst du ja dazu schreiben, wie das Buch (?) heißt, damit man in so einem Fall auch danach suchen kann? Viele Grüße, Kiddycat\(\endgroup\)
 

Re: Voronoi-Diagramme und Anwendungen
von: mire2 am: So. 11. April 2010 14:27:07
\(\begingroup\)Hallo Kiddy! Hmm, ich lese gerade Deinen Kommentar und stelle fest, dass der Autor sich seit fast drei Jahren nicht mehr auf dem MP eingeloggt hat. Da ist von dieser Seite wohl eher weniger mit Hilfe zu rechnen, aber was Du für ein Glück hast, dass es MICH gibt. 😁 Eine kurze Recherche auf der Hauptseite des verlinkten Artikels förderte das hier zutage: www.cise.ufl.edu/tr/REP-1994-139/ Das sollte wohl der neue Ort des verlinkten Artikels sein. Sonntäglichen Gruß Michael\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]