In der Mathematik ist ein Diagramm von Voronoi eine spezielle Art der Zergliederung eines gegebenen Raums, z.B, eines metrischen Raums, der durch Entfernungen zu einer angegebenen Familie von Gegenständen (Teilmengen) im Raum bestimmt ist. Diese Gegenstände werden gewöhnlich die Seiten oder die Generatoren genannt (aber andere Namen, werden wie "Samen" verwendet), und zu jedem solchem Gegenstand vereinigt man eine entsprechende Zelle von Voronoi, nämlich der Satz des ganzen

Punkte im gegebenen Raum, dessen Entfernung zum gegebenen Gegenstand nicht größer ist als ihre Entfernung zu den anderen Gegenständen. Es wird nach Georgy Voronoi genannt, und wird auch einen Voronoi tessellation, eine Zergliederung von Voronoi oder einen Dirichlet tessellation (nach Lejeune Dirichlet) genannt. Diagramme von Voronoi können in einer Vielzahl von Feldern in der Wissenschaft und Technologie sogar in der Kunst gefunden werden, und sie haben zahlreiche praktische und theoretische Anwendungen gefunden. Es ist die Technik, die die Abteilung solcher mehrdimensionalen Räume in Subräume ermöglicht.

Der einfachste Fall

Im einfachsten und vertrautesten Fall (gezeigt im ersten Bild) wird uns ein begrenzter Satz von Punkten {p..., p} im Euklidischen Flugzeug gegeben. In diesem Fall

jede Seite p ist einfach ein Punkt, und seine entsprechende Zelle von Voronoi (hat auch Gebiet von Voronoi oder Zelle von Dirichlet genannt) R, aus allen Punkten bestehend, deren Entfernung zu p nicht größer ist als ihre Entfernung zu jeder anderen Seite. Jede solche Zelle wird bei der Kreuzung von Halbräumen erhalten, und folglich ist es ein konvexes Vieleck. Die Segmente des Diagramms von Voronoi sind alle Punkte im Flugzeug, die zu den zwei nächsten Seiten gleich weit entfernt sind. Die Voronoi Scheitelpunkte (Knoten) sind die Punkte, die zu drei (oder mehr) Seiten gleich weit entfernt sind.

Formelle Definition

Lassen Sie, ein Raum (ein nichtleerer Satz) ausgestattet mit einer Entfernungsfunktion zu sein. Lassen Sie, eine Reihe von Indizes zu sein und zu lassen, ein Tupel (bestellte Sammlung) nichtleerer Teilmengen (die Seiten) im Raum zu sein. Die Voronoi Zelle oder Gebiet von Voronoi, vereinigt mit der Seite ist der Satz aller Punkte, in deren Entfernung dazu nicht größer ist als ihre Entfernung zu den anderen Seiten, wo jeder Index ist, der davon verschieden ist. Mit anderen Worten, wenn die Entfernung zwischen dem Punkt und der Teilmenge, dann anzeigt

:

Das Voronoi Diagramm ist einfach das Tupel von Zellen. Im Prinzip können sich einige der Seiten schneiden und sogar zusammenfallen (eine Anwendung wird unten für Seite-Darstellen-Geschäfte beschrieben), aber gewöhnlich, wie man annimmt, sind sie zusammenhanglos. Außerdem ungeheuer wird vielen Seiten in der Definition erlaubt (diese Einstellung hat Anwendungen in der Geometrie von Zahlen und Kristallographie), aber wieder in vielen Fällen nur begrenzt werden viele Seiten betrachtet.

Im besonderen Fall, wo der Raum ein begrenzter dimensionaler Euklidischer Raum ist, ist jede Seite ein Punkt, es gibt begrenzt viele Punkte, und sie alle sind dann verschieden die Zellen von Voronoi sind konvexer polytopes, und sie können in einer kombinatorischen Weise vertreten werden, ihre Scheitelpunkte, Seiten, 2-dimensionale Gesichter usw. zu verwenden. Manchmal wird die veranlasste kombinatorische Struktur das Diagramm von Voronoi genannt. Jedoch im Allgemeinen können die Zellen von Voronoi nicht konvex oder sogar verbunden sein.

Illustration

Als eine einfache Illustration, denken Sie eine Gruppe von Geschäften in einer flachen Stadt. Nehmen Sie an, dass wir die Zahl von Kunden eines gegebenen Geschäftes schätzen wollen. Mit allen sonst gleich (Preis, Produkte, Qualität des Dienstes, usw.) zu sein, ist es angemessen anzunehmen, dass Kunden ihr bevorzugtes Geschäft einfach durch Entfernungsrücksichten wählen: Sie werden zum Geschäft gelegen am nächsten zu ihnen gehen. In diesem Fall die Zelle von Voronoi

eines gegebenen Geschäftes kann verwendet werden, für eine Überschlagsrechnung auf der Zahl von potenziellen Kunden zu geben, die zu diesem Geschäft gehen (der durch den Punkt in unserer flachen Stadt modelliert wird).

Bis jetzt wurde es angenommen, dass die Entfernung zwischen Punkten in der Stadt mit der Standardentfernung, d. h. dem vertrauten gemessen wird

Euklidische Entfernung:

.

Jedoch, wenn wir den Fall in Betracht ziehen, wohin Kunden nur zu den Geschäften durch ein Fahrzeug gehen und die Verkehrspfade zu und Äxte, wie in Manhattan parallel sind, dann wird eine realistischere Entfernungsfunktion die Entfernung, nämlich sein

.

Das zeigt, dass die Zellen von Voronoi bedeutsam vom verwendeten metrischen abhängen.]]

Eigenschaften

• Der Doppelgraph für ein Diagramm von Voronoi (im Fall von einem Euklidischen Raum mit Punkt-Seiten) entspricht der Triangulation von Delaunay für denselben Satz von Punkten.
• Das nächste Paar von Punkten entspricht zwei angrenzenden Zellen im Diagramm von Voronoi.
• Nehmen Sie an, dass die Einstellung das Euklidische Flugzeug ist und eine Gruppe von verschiedenen Punkten gegeben werden. Dann sind zwei Punkte auf dem konvexen Rumpf angrenzend, wenn, und nur wenn ihre Zellen von Voronoi eine ungeheuer lange Seite teilen.
• Wenn der Raum ein normed Raum ist und die Entfernung zu jeder Seite erreicht wird (z.B, wenn eine Seite ein Kompaktsatz oder ein geschlossener Ball ist), dann kann jede Zelle von Voronoi als eine Vereinigung von Liniensegmenten vertreten werden, die von den Seiten ausgehen. Wie gezeigt, dort hält dieses Eigentum nicht notwendigerweise, wenn die Entfernung nicht erreicht wird.
• Unter relativ allgemeinen Bedingungen (ist der Raum ein vielleicht unendlicher dimensionaler gleichförmig konvexer Raum, kann es ungeheuer viele Seiten einer allgemeinen Form, usw. geben) Zellen von Voronoi genießen ein bestimmtes Stabilitätseigentum: Ein Kleingeld in den Gestalten der Seiten, z.B, eine Änderung, die durch eine Übersetzung oder Verzerrung verursacht ist, gibt ein Kleingeld in Form der Zellen von Voronoi nach. Das ist die geometrische Stabilität von Diagrammen von Voronoi. Wie gezeigt, dort hält dieses Eigentum im Allgemeinen nicht, selbst wenn der Raum zweidimensional (aber ungleichförmig konvex, und insbesondere nicht-euklidisch ist) und die Seiten Punkte sind.

Geschichte und Forschung

Der informelle Gebrauch von Diagrammen von Voronoi kann zurück Descartes 1644 verfolgt werden. Dirichlet hat 2-dimensionale und 3-dimensionale Diagramme von Voronoi in seiner Studie von quadratischen Formen 1850 verwendet.

Britischer Arzt John Snow hat ein Diagramm von Voronoi 1854 verwendet, um zu illustrieren, wie die Mehrheit von Leuten, die in der Cholera-Epidemie von Soho gestorben sind, näher an der angesteckten Pumpe der Broad Street gelebt hat als zu jeder anderen Wasserpumpe.

Diagramme von Voronoi werden nach dem russischen Mathematiker Georgy Fedoseevich Voronoi (oder Voronoy) genannt, wer definiert hat und den allgemeinen n-dimensional Fall 1908 studiert hat. Diagramme von Voronoi, die in der Geophysik und Meteorologie verwendet werden, um räumlich verteilte Daten zu analysieren (wie Niederschlag-Maße) werden Vielecke von Thiessen nach dem amerikanischen Meteorologen Alfred H. Thiessen genannt. In der kondensierten Sache-Physik sind solche tessellations auch bekannt als Wigner-Seitz Einheitszellen. Voronoi tessellations des gegenseitigen Gitters von Schwüngen wird Zonen von Brillouin genannt. Für allgemeine Gitter in Lüge-Gruppen werden die Zellen einfach grundsätzliche Gebiete genannt. Im Fall von allgemeinen metrischen Räumen werden die Zellen häufig metrische grundsätzliche Vielecke genannt.

Andere gleichwertige Namen für dieses Konzept (oder besondere wichtige Fälle davon): Polyeder von Voronoi, Vielecke von Voronoi, Gebiet (E) des Einflusses, der Zergliederung von Voronoi, Voronoi tessellation (s), Dirichlet tessellation (s).

Beispiele

Voronoi tessellations von regelmäßigen Gittern von Punkten in zwei oder drei Dimensionen verursachen viele vertraute tessellations.

• Ein 2. Gitter gibt eine unregelmäßige Honigwabe tessellation mit gleichen Sechsecken mit der Punkt-Symmetrie; im Fall von einem regelmäßigen Dreiecksgitter ist es regelmäßig; im Fall von einem rechteckigen Gitter nehmen die Sechsecke zu Rechtecken in Reihen und Säulen ab; ein Quadratgitter gibt den regelmäßigen tessellation von Quadraten; bemerken Sie, dass die Rechtecke und die Quadrate auch durch andere Gitter erzeugt werden können (zum Beispiel, gibt das Gitter, das durch die Vektoren (1,0) und (1/2,1/2) definiert ist, Quadrate). Sieh hier für ein dynamisches Sehbeispiel.
• Ein einfaches Kubikgitter gibt die Kubikhonigwabe.
• Ein sechseckiges Ende-gepacktes Gitter gibt einen tesselation des Raums mit trapezo-rhombischem dodecahedra.
• Ein Gesicht - Kubikgitter gibt einen tessellation des Raums mit rhombischem dodecahedra.
• Ein Körper - Kubikgitter gibt einen tessellation des Raums mit gestutztem octahedra.
• Parallele Flugzeuge mit regelmäßigen Dreiecksgittern, die nach jedem die Zentren der anderen ausgerichtet sind, geben die sechseckige prismatische Honigwabe.
• Bestimmter Körper hat im Mittelpunkt gestanden tetragonal Gitter geben einen tessellation des Raums mit rhombo-sechseckigem dodecahedra.

Für den Satz von Punkten (x, y) mit x in einem getrennten Satz X und y in einem getrennten Satz Y, bekommen wir rechteckige Ziegel mit den Punkten nicht notwendigerweise an ihren Zentren.

Höherwertige Voronoi Diagramme

Obwohl eine normale Zelle von Voronoi als der Satz von Punkten definiert wird, die an einem einzelnen Punkt in S, eine n-te Ordnung am nächsten sind, wird Zelle von Voronoi als der Satz von Punkten definiert, die einen besonderen Satz von N-Punkten in S haben, weil sein n am nächsten benachbart ist. Höherwertige Voronoi Diagramme unterteilen auch Raum.

Höherwertige Voronoi Diagramme können rekursiv erzeugt werden. Um die N-Ordnung Diagramm von Voronoi vom Satz S zu erzeugen, fangen Sie mit an (n − 1) - bestellen Diagramm und ersetzen jede Zelle, die durch X = {x, x..., x} mit einem Diagramm von Voronoi erzeugt ist, das auf dem Satz S &minus erzeugt ist; X.

Weitester Punkt Voronoi Diagramm

Weil eine Reihe von n (n−1) hinweist - befehlen, dass Diagramm von Voronoi einen weitesten Punkt Diagramm von Voronoi genannt wird.

Für einen gegebenen Satz von Punkten S = {p, p..., p} der weiteste Punkt teilt Diagramm von Voronoi das Flugzeug in Zellen, in denen derselbe Punkt von P der weiteste Punkt ist. Bemerken Sie, dass ein Punkt von P eine Zelle im weitesten Punkt Diagramm von Voronoi hat, wenn, und nur wenn es ein Scheitelpunkt des konvexen Rumpfs von P ist. Lassen Sie so H = {h, h..., h} der konvexe Rumpf von P sein wir definieren den weitesten Punkt Diagramm von Voronoi als die Unterteilung des Flugzeugs in k Zellen, ein für jeden Punkt in H mit dem Eigentum, dass ein Punkt q in der Zelle entsprechend einer Seite h wenn und nur wenn dist (q, h)> dist (q, p) für jeden p &isin liegt; S mit h  p. Wo dist (p, q) die euklidische Entfernung zwischen zwei Punkten p und q ist.

Generalisationen und Schwankungen

Wie einbezogen, durch die Definition können Zellen von Voronoi für die Metrik außer Euklidisch (wie Mahalanobis oder Manhattan) Entfernungen definiert werden. Jedoch in diesen Fällen können die Grenzen der Zellen von Voronoi mehr kompliziert sein als im Euklidischen Fall, da der gleich weit entfernte geometrische Ort für zwei Punkte scheitern kann, Subraum von codimension 1, sogar im 2-dimensionalen Fall zu sein.

Ein belastetes Diagramm von Voronoi ist dasjenige, in dem die Funktion eines Paares von Punkten, eine Zelle von Voronoi zu definieren, eine Entfernungsfunktion ist, die durch multiplicative oder zusätzliche Generator-Punkten zugeteilte Gewichte modifiziert ist. Im Gegensatz zum Fall vom definierten Verwenden von Zellen von Voronoi einer Entfernung, die ein metrischer in diesem Fall ist, können einige der Zellen von Voronoi leer sein.

Das Voronoi Diagramm von N-Punkten im d-dimensional Raum verlangt Abstellraum. Deshalb sind Diagramme von Voronoi häufig für d> 2 nicht ausführbar. Eine Alternative soll ungefähre Diagramme von Voronoi verwenden, wo die Zellen von Voronoi eine krause Grenze haben, der näher gekommen werden kann. Eine andere Alternative ist, wenn jede Seite ein krauser Kreis ist und infolgedessen die Zellen kraus auch werden.

Diagramm von Voronoi ist auch mit anderen geometrischen Strukturen wie die mittlere Achse verbunden (der Anwendungen in der Bildsegmentation, der optischen Charakter-Anerkennung und den anderen rechenbetonten Anwendungen gefunden hat), gerades Skelett und Zonendiagramme.

Anwendungen

• Eine der frühen Anwendungen von Diagrammen von Voronoi war durch John Snow, um die Epidemiologie des 1854-Cholera-Ausbruchs der Broad Street in Soho, England zu studieren. Er hat die Korrelation zwischen Gebieten auf der Karte Londons mit einer besonderen Wasserpumpe und den Gebieten mit den meisten Todesfällen wegen des Ausbruchs gezeigt.
• Eine Punkt-Positionsdatenstruktur kann oben auf dem Diagramm von Voronoi gebaut werden, um auf nächste Nachbarabfragen zu antworten, wo man den Gegenstand finden will, der an einem gegebenen Anfragenpunkt am nächsten ist. Nächste Nachbarabfragen haben zahlreiche Anwendungen. Zum Beispiel könnte man das nächste Krankenhaus oder den ähnlichsten Gegenstand in einer Datenbank finden wollen. Eine große Anwendung ist Vektor quantization, allgemein verwendet in der Datenkompression.
• Mit einem gegebenen Diagramm von Voronoi kann man auch den größten leeren Kreis unter einer Reihe von Punkten, und in einem Umgeben-Vieleck finden; z.B, einen neuen Supermarkt so weit möglich von allen vorhandenen zu bauen, in einer bestimmten Stadt liegend.
• Diagramme von Voronoi zusammen mit dem weitesten Punkt Diagramme von Voronoi werden für effiziente Algorithmen verwendet, um die Rundung von einer Reihe von Punkten zu schätzen.
• Das Voronoi Diagramm ist in der Polymer-Physik nützlich. Es kann verwendet werden, um freies Volumen des Polymers zu vertreten.
• Es wird auch in Abstammungen der Kapazität eines Radionetzes verwendet.
• Die Voronoi-Annäherung wird auch zum guten Gebrauch in der Einschätzung der Rundheit / Rundung gestellt, während man assesing den dataset von einer koordinatenmessenden Maschine verwendet.
• In der Klimatologie werden Diagramme von Voronoi verwendet, um den Niederschlag eines Gebiets zu berechnen, das auf einer Reihe von Punkt-Maßen gestützt ist. In diesem Gebrauch werden sie allgemein Vielecke von Thiessen genannt.
• Diagramme von Voronoi werden verwendet, um die Wachstumsmuster von Wäldern und Waldbaldachinen zu studieren, und können auch im Entwickeln prophetischer Modelle für Waldfeuer nützlich sein.
• Diagramme von Voronoi werden auch in der Computergrafik verwendet, um einige Arten organisch aussehender Texturen verfahrensrechtlich zu erzeugen.
• In der autonomen Roboter-Navigation werden Diagramme von Voronoi verwendet, um klare Wege zu finden. Wenn die Punkte Hindernisse sind, dann werden die Ränder des Graphen die Wege weiter von Hindernissen (und theoretisch irgendwelche Kollisionen) sein.
• In der rechenbetonten Chemie werden Zellen von Voronoi, die durch die Positionen der Kerne in einem Molekül definiert sind, verwendet, um Atomanklagen zu schätzen. Das wird mit der Deformierungsdichte-Methode von Voronoi getan.
• In der Material-Wissenschaft werden polykristallene Mikrostrukturen in der metallischen Legierung mit Voronoi tessellations allgemein vertreten.
• Vielecke von Voronoi sind im Bergwerk verwendet worden, um die Reserven von wertvollen Materialien, Mineralen oder anderen Mitteln zu schätzen. Forschungsdrillholes werden als der Satz von Punkten in den Vielecken von Voronoi verwendet.
• Im Maschinenlernen werden Diagramme von Voronoi verwendet, um 1-NN Klassifikationen zu tun.

Siehe auch

Algorithmen

• Algorithmus von Bowyer-Watson - ein Algorithmus, für ein Diagramm von Voronoi in jeder Zahl von Dimensionen zu erzeugen.
• Der Algorithmus des Glückes - ein O (n Klotz (n)) Algorithmus, für ein Diagramm von Voronoi von einer Reihe von Punkten in einem Flugzeug zu erzeugen.
• Algorithmus von Lloyd's

Zusammenhängende Themen

• Centroidal Voronoi tessellation
• Rechenbetonte Geometrie
• Triangulation von Delaunay
• Mathematisches Diagramm

• Natürliche Nachbarinterpolation
• Am nächsten sucht Nachbar
• Nah-Nachbarinterpolation
• Pol von Voronoi

Referenzen

• Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Räumlicher Tessellations - Konzepte und Anwendungen von Voronoi Diagrammen. 2. Ausgabe. John Wiley, 2000, internationale 671-Seite-Standardbuchnummer 0-471-98635-6
• Daniel Reem (2011). Die geometrische Stabilität von Diagrammen von Voronoi in Bezug auf kleine Änderungen der Seiten. Volle Version: arXiv 1103.4125 (2011), Verlängerter Auszug: in Verhandlungen des 27. Jährlichen ACM Symposiums auf der Rechenbetonten Geometrie (SoCG 2011), Seiten 254-263.

• Kapitel 7: Voronoi Diagramme: Seiten 147-163. Schließt eine Beschreibung des Algorithmus von Fortune ein.

Links

• Interaktiver Echtzeitvoronoi / Diagramme von Delaunay mit Draggable-Punkten, Java 1.0.2, 1996-1997
• Interaktive Echtzeitdiagramme von Voronoi und Delaunay mit der Quelle codieren
• Demo für die verschiedene Metrik
• Mathworld auf Diagrammen von Voronoi
• Qhull, für das Diagramm von Voronoi im 2., 3. usw. zu schätzen.
• Voronoi Diagramme: Anwendungen von der Archäologie bis Zoologie

• Voronoi Diagramme in CGAL, die rechenbetonte Geometrie-Algorithmus-Bibliothek
• Voronoi Website: das Verwenden von Diagrammen von Voronoi für die Raumanalyse
• Mehr Diskussionen und Bildergalerie auf centroidal Voronoi tessellations
• Voronoi Diagramme von Ed Pegg dem Jüngeren. Jeff Bryant, und Theodore Gray, Wolfram-Demonstrationsprojekt.
• Nette Erklärung des voronoi Diagramms und Sehdurchführung des Algorithmus des Glückes