Diskussion:Voronoi-Diagramm

Namensherkunft Voronoi

Eine Frage: Warum heißen die Diagramme Voronoi-Diagramme, obwohl der Mathematiker "Woronoi" hieß? Mir ist schon klar, dass das russische "B" beides bedeuten kann, aber was ist denn nun richtig? In der Literatur wird immer vom "Voronoi-Diagramm" gesprochen.

Schätze das liegt daran, dass im Englischen das kyrillische "B" immer zu "V" wird und der Begriff "Voronoi-Diagramm" durch die englische und ansonsten konsistent zur englischen geführten Literatur geprägt ist. Den Herrn selbst kann man stattdessen direkt aus dem kyrillischen übersetzen, deswegen mit W, wie üblich in Deutschland. --IdS 18:56, 6. Mär. 2010 (CET)

Außerdem liest man oft von einem Mathematiker "M.G. Voronoi", der 1908 das Voronoi-Diagramm-Konzept entwickelt hat. Leider habe ich keine verlässlichen Quellen gefunden. Weiß da jemand genaues?

Vielleicht von sowas wie "Mister/Master/Magister... Georgi Voronoi"? Hab ich allerdings noch nie gelesen --IdS 18:56, 6. Mär. 2010 (CET)

Überschneidung Wigner-Seitz-Zelle? (erl.)

Sollte man Voronoi-Diagramm und Wigner-Seitz-Zelle zusammenführen? --Keinstein 17:15, 15. Sep 2006 (CEST)

Ich finde nicht, dass man das sollte. Denn das ist eben nur ein Spezialfall. So wie Pferd ein Spezialfall von Säugetier ist, und trotzdem hat es seinen eigenen Artikel.(ok, hinkt vielleicht ein bischen der Vergleich^^)--Falk 03:52, 7. Mär. 2007 (CET)

Ja, aber ich hätte mich über einen Verweis auf Wigner-Seitz-Zelle gefreut, nicht jeder liest die Diskussionsseite und findet das Wort dann hier. Außerdem werden in vielen Vorlesungen beide Begriffe verwendet und mir war neu, dass das 2 verschiedene Dinge sind. Wenn es keinen stört, mache ich das, man kann es ja hinterher wieder löschen wenn es stört.92.226.207.228 12:41, 28. Jul. 2009 (CEST)

Den Verweis gibt auf die Wigner-Seitz-Zelle gibt es mittlerweile.--GURKEdeluxe (Diskussion) 20:09, 22. Feb. 2020 (CET)

Dieser Abschnitt kann archiviert werden. GURKEdeluxe (Diskussion) 20:09, 22. Feb. 2020 (CET)

Voronoi-Interpolation

Ich bin von "Voronoi-Interpolation" herkommend auf dieser Seite gelandet. Leider kann ich mit den Informationen in den beiden Artikeln nicht viel anfangen, irgendwie fehlen mir da noch einige Grundlagen. Kann man das noch ergänzen, so dass auch nicht-Mathestudenten verstehen um was es geht?

Umfang des Artikels

Also ich finde den Artikel zu klein geraten, was ist z.B. mit Voronoi Diagrammen zu anderen Metriken als der euklidischen? Was ist mit inversen Voronoi Diagrammen? Vielleicht sollte man auch mal erwähnen, dass man Voronoi Diagramme nicht nur zu Punktmengen, sondern auch zu anderen Strukturen wie Liniensegmenten und Polygonen machen kann (kann man nämlich für Roboter-Pfadplanung brauchen). Ich bin kein Mathestudent, aber mir ist der Artikel definitiv zu wenig formal!

Ich finde auch nicht, dass der Artikel zu formal ist (das setzt nämlich Formalismen voraus ;)) und weiß auch nicht, was daran, für nicht-Mathemamatiker, nicht verständlich ist. Ich bin schließlich auch keiner. Eigentlich ist der Sachverhalt gut erklärt. Was mir aber fehlt, abgesehen von dem, was mein direkter Vorredner schon erwähnt hat, sind konkrete Algorithmen, die auch effizienter sind als der naive Ansatz mit O(n^2), à la O(n log(n)). Außerdem sollte vielleicht erwähnt werden, dass Voronoi-Diagramme das Postamt-Problem (meines Wissens sogar mit optimalem Zeitaufwand) lösen. Auch würde ich mir zumindest Links auf Problemstellungen, bei denen Voronoi-Diagramme/Strukturen bei der Lösung behilflich sind, oder die Lösung selbst darstellen, wünschen (wie z.B. die von meinem Vorredner erwähnte Roboter-Pfadplanung). Ich verstehe leider noch nicht genügend von dem Thema, um den Artikel aktiv zu verbessern. Aber der ein oder andere wird sich doch wohl finden. Warum sind bei WP manche Themen eigentlich so unpopulär?^^ Gruß --Falk 03:46, 7. Mär. 2007 (CET)

Mir erscheint das alles doch sehr einseitig auf Geowissenschaften bezogen, oder um mich meinen Vorrednern anzuschließen, zu wenig formal. Darüber hinaus ist er unvollständig, was zb. die Ordnung eines Voronoi-Diagramms betrifft. Leider fehlt mir dahingehend auch noch etwas Wissen, um den Artikel ordentlich zu ergänzen. Sobald sich das ändert sehe ich mir das noch mal an, wenn sich vorher jemand dazu findet, umso besser :-) Gruß

Auch ich bin der Meinung, dass da ein Experte mal mehr dazu schreiben muss. Ich hab als Informatiker zwar entsprechende Quellen, aber keine Idee, wie man die mathematische-informationstechnische Anwendung und Definition in das Vorhandene einbauen soll. --D135-1r43 21:00, 20. Nov. 2007 (CET)

Versionsgeschichte Polygon-Methode für Zusammenführung mit Voronoi-Diagramm (erl.)

1. (Aktuell) (Vorherige) 13:51, 25. Jun 2006 Dickbauch (Diskussion | Beiträge) (LA+)
2. (Aktuell) (Vorherige) 10:08, 10. Apr 2006 Zumbo (Diskussion | Beiträge) (+Unverständlich)
3. (Aktuell) (Vorherige) 00:57, 19. Dez 2005 Saperaud (Diskussion | Beiträge) (neu, selbst)

-- Universaldilettant 00:35, 1. Jul 2006 (CEST)

Ist zusammengeführt.--GURKEdeluxe (Diskussion) 20:10, 22. Feb. 2020 (CET)

Dieser Abschnitt kann archiviert werden. GURKEdeluxe (Diskussion) 20:10, 22. Feb. 2020 (CET)

Neufassungsversuch (erl.)

Ich habe versucht den Artikel nach bestem Wissen und Gewissen neu zu verfassen, leider vergas ich mich vorher anzumelden. Ich musste einige Sachen herausnehmen, was mir ja immer leid tut aber ich habe einfach nicht verstanden, was damit gemeint war. Ich hoffe vorige Autoren damit nicht verärgert zu haben aber der Artikel ist eh noch als ungesichtet markiert. Ich habe versucht ihn verständlich zu formulieren, was hoffentlich gelungen ist. Sowas kann man selbst immer schwer beurteilen. Dummerweise habe ich deshalb den Begriff Zentrum eingeführt, den ich so in der deutschsprachigen Literatur nicht gefunden habe, mir aber eine einfache Möglichkeit gab die vorgegebene Punktemenge (die Zentren) von den sonstigen Punkten des Raumes zu unterscheiden.

Warum ich eine Neufassung gewagt habe bzw. eine halbe Neufassung ist:

• Titel Voronoi-Diagramm und es wird in der Einleitung nur vom Voronoi-Polygon gesprchen
• Sprachlich teilweise sehr schwach, wobei ich nicht garantieren kann das ich da so viel besser bin
• Erklärungen wurden nur halbherzig bis gar nicht gemacht
• Es wurden insbesondere Dinge ins Zentrum gestellt, die mit den Voronoi-Diagrammen nur sekundär was zu tun haben (Bsp. Messwerte), viel allgemeiner sind Punkte

Ich hoffe das der Artikel akzeptiert wird und wünsche mir nat. eifrige Mitarbeit zu seiner Verbesserung. Sanches 20:10, 8. Jul. 2008 (CEST)

Hier nochmal meine Unterschrifft als IP. Ich habe ihn also wirklich geschrieben. (Ref. to Sanches) 81.173.172.245 20:13, 8. Jul. 2008 (CEST)

Dieser Abschnitt kann archiviert werden. GURKEdeluxe (Diskussion) 20:11, 22. Feb. 2020 (CET)

Definition

Die mathematische Definition, im aktuellen Entwurf, scheint mir zwar auf den ersten Blick korrekt zu sein, allerdings bezieht sie sich nur auf den $\mathbb {R} ^{2}$. Besser wäre es, wenn das gleich auf den $\mathbb {R} ^{n}$ verallgemeinert würde. Grüße Falk 13:34, 10. Jul. 2008 (CEST)

Nachtrag: Vielleicht hab' ich nen Denkfehler, aber müsste es anstatt

$VR(p,S)=\bigcup _{q\in S\setminus \{p\}}D(p,q)$

nicht

$VR(p,S)=\bigcap _{q\in S\setminus \{p\}}D(p,q)$

heißen? Denn, nehmen wir z. B. drei Punkte:

$P_{l}(-1,0);P_{m}(0,0);P_{r}(1,0)$

Dann wäre -- nach Definition im Entwurf --

$VR(P_{m},\{P_{l},P_{m},P_{r}\})=D(P_{m},P_{l})\cup D(P_{m},P_{r})$

mit

$D(P_{m},P_{l})=\{x\in \mathbb {R} ^{2}:x\in (-0.5,\infty )\times (-\infty ,\infty )\}$ (also alle Punkte, deren x-Komponente > -0.5 ist)

und

$D(P_{m},P_{r})=\{x\in \mathbb {R} ^{2}:x\in (-\infty ,0.5)\times (-\infty ,\infty )\}$ (also alle Punkte, deren x-Komponente < 0.5 ist).

Und das würde wiederum

$VR(P_{m},\{P_{l},P_{m},P_{r}\})=\{x\in \mathbb {R} ^{2}:(-0.5,\infty )\times (-\infty ,\infty )\cup (-\infty ,0.5)\times (-\infty ,\infty )\}$

ergeben. Da die eine Punktmenge nach links und die andere nach rechts offen ist, die beiden aber eine nicht lehre Schnittmenge haben (die Punkte mit den x-Komponenten im Intervall [-0.5,0.5]), gilt doch

$VR(P_{m},\{P_{l},P_{m},P_{r}\})=\mathbb {R} ^{2}$,

was ja wohl nicht stimmen kann, da es ja so keinen Platz mehr für die beiden anderen übrigen Regionen, die von dieser distinkt sein müssen, gibt. Hätte man hier die Schnittmenge aller $D(P_{m},\cdot )$, anstatt der Vereinigung, gebildet, so wäre das richtige Ergebnis herausgekommen... Grüße Falk 14:34, 10. Jul. 2008 (CEST)

Ich hab' Vereinigung der Halbebenen jetzt im Text und in der Formel durch einen Schnitt ersetzt. Die Vereinigung der Halbebenen gibt für geschlossene Regionen einfach wieder nur den $\mathbb {R} ^{2}$! Bitte lest erstmal, ob sich jemand zu dem Thema in der Diskussion geäußert hat, bevor Ihr das als gesichtet markiert! Oder besser noch: Prüft ob das stimmt, was da ergänzt wurde! Grüße Falk 09:52, 11. Jul. 2008 (CEST)

Ups, ja tut mir leid war ein flüchtlingsfehler Sanches 14:58, 11. Jul. 2008 (CEST)

Joa, ist ja nicht so schlimm. bei \cup und \cap vertippe ich mich erstens auch ständig und zweites kann man da schnell mal gedanklich durcheinander kommen. Da ist dann allerdings auch der Nachteil der gesichteten Versionen: Irgendwer markiert es vorzeitig als gesichtet (was ich auch niemandem vorwerfen will -- jeder macht eben Fehler, zumal mir das auf den ersten Blick auch eingeleuchtet hatte^^) und wenn man es dann korrigiert, bleibt es manchmal Tage lang falsch stehen. Aus dem Anlass hab' ich gerade Sichtungsrechte beantragt -- aber ob das bei meinen 50 - 60 Artikel-Edits was wird, ist die Frage (ist eh nen komisches Kriterium mit den 200 Artikel-Edits, zumal ich mehr als zwei Jahre dabei bin...).

Auf jeden Fall bin ich froh, dass sich mal einer der formalen Definition angenommen hat! Grüße Falk 15:17, 11. Jul. 2008 (CEST)

To Do

Da hier mal wieder ein bisschen was passiert ist, schreibe ich einfach mal, was mir an dem Artikel persönlich noch fehlt.

Es sollte mehr darauf eingegangen werden, wozu Voronoi-Diagramme/-Strukturen eigentlich gut sind. Z. B. lösen sie das Postamtproblem optimal (in der richtigen Struktur gespeichert, vorausgesetzt): aufbauen der Struktur(Regionen um die jeweiligen Postämter) O(n log n); finden des nächsten PA zu einem gegebenen Punkt O(1)O(log n). Weiterhin habe ich gelesen, dass sich Voronoi-Strukturen für Kürzeste-Wege-Probleme verwenden lassen. Weitere Probleme, die durch VRs gelöst werden, sind wünschenswert (und das sind sicher noch einige andere).

Desweiteren fehlen Algorithmen (die Beispiele im Netz sind oft schlecht verständlich) zum (effizienten) Aufbau. Vielleicht erstmal ein trivialer Ansatz, der Über die Definition geht (dürfte O(n^2) haben) Dann der Devide-and-Conquer Algorithmus O(n log n): Teilen der Punktmenge durch einen Schnitt möglichst in der Mitte (Abbruch wenn nur ein Punkt übrig ist) und anschließendes mergen:

Voronoi V(S):
    if |S|=1:
        return new Voronoi(S) //VD, was aus dem einen Punkt in S besteht
    else:
        teile(S,Sl,Sr) //Punktmenge in Sl und Sr zerlegen
        return merge(V(Sl),V(Sr))> //zwei VDs werden zu einem gemerged

Das Mergen ist leider nicht trivial. Ich sitze gerade an einer Implementierung. Sobalt ich merge optimal hinbekommen habe, fließt das hier als Pseudocode hierher zurück. Und dann ist sicherlich noch das Sweap-Line Verfahren von Belang, was ebenfalls asympthotisch optimal ist.

Aso, auf jeden Fall fehlt auch noch die allgemeine Definition für den $R^{n}$.

Grüße Falk 02:18, 12. Jul. 2008 (CEST)

Zusammenhang k-Means-Algorithmus

Faktisch berechnet der k-Means-Algorithmus ein aus Voronoi-Zellen bestehendes Clustering. (Technisch berechnet er zwar Mittelpunkte, aber die Zuordnung zu Clustern entspricht eben genau den Voronoi-Zellen!). Das sollte in diesen Artikel noch eingearbeitet werden. Ich habe auf die Schnelle aber nicht gesehen wo das am Besten geschehen kann. Freiwillige vor! --Chire 12:23, 16. Jan. 2011 (CET)

Schreibweise mit ï ? (erl.)

Dachte bis jetzt immer es schreibt sich Voronoï mit Doppelpunkt auf dem "i". Franz. Wikipedia macht das auch: http://fr.wikipedia.org/wiki/Diagramme_de_Vorono%C3%AF ist aber damit die einzige afaik. In einem englischen Buch hatte ich das auch so gesehen. Muss wohl an der Eindeutschung des Namens liegen (wie auch der Unterschied von "w" zu "v" der ja schon diskutiert wurde) im Gegensatz zur Einfränzösischung. Blart 17:48, 25. Feb. 2011 (CET)

Die französische Wikipedia [1] schreibt zu ï, dass dieses Zeichen die korrekte Aussprache kennzeichnet. Ohne die zwei Punkte würden Franzosen das Wort Voronoi eher wie "voronwoa" aussprechen. Diese Kenntlichmachung der korrekten Aussprache ist im Deutschen (wie auch im Englischen) nicht notwendig. --Chris☂ 18:17, 25. Feb. 2011 (CET)

Dieser Abschnitt kann archiviert werden. GURKEdeluxe (Diskussion) 20:12, 22. Feb. 2020 (CET)

Praktisches Beispiel? (erl.)

Ätzstrukturen

Wäre das nebenstehende Bild nicht eine interessante, praktisch gewonnene Aufnahme für diesen Artikel? Ausgangssituation: das Metall Vanadium liegt flüssig vor, via Zufall entstehen Kristallkeime, die so lange zu Kristallen wachsen, bin diese die Korngrenzen der Nachbarkristallite erreichen. Dann ist das Wachstum beendet und das flüssige Metall erstarrt. -- Alchemist-hp 18:12, 4. Sep. 2011 (CEST)

Das sieht tatsächlich wie ein Voronoi-Diagramm aus. Aber es wäre doch schon eher Zufall, wenn es eines wäre. Das Voronoi-Diagramm hat in der Physik schon eine Bedeutung und bestimmte Optimierungsprozesse in selbstorganisierten Strukturen könnten durchaus eine Voronoi-Diagramm-Struktur zeigen. Aber das kristalline Wachstum folgt ganz anderen Gesetzmäßigkeiten und orientiert sich an der Kristallstruktur und an Gitterstörstellen. Es gibt hier außerdem mehrere Korngrenzen mit einer konkav nach innen geknickten Randlinie, was zeigt, dass es kein Voronoi-Diagramm ist. --Chris☂ 18:31, 4. Sep. 2011 (CEST)

OK, Danke für die Aufklärung. Das sah für mich stark nach einem Voronoi-Diagramm aus. -- Alchemist-hp 19:00, 4. Sep. 2011 (CEST)

Dieser Abschnitt kann archiviert werden. GURKEdeluxe (Diskussion) 20:13, 22. Feb. 2020 (CET)

Berechnungsalgorithmus

Der im Artikel vorhandene Berechnungsalgorithmus ist relativ ungünstig, unter anderem weil er die Berechnung einer konvexen Hülle in $n+1$ Dimensionen (bzw. dort drei Dimensionen) voraussetzt. Da die überwiegende Mehrheit aller einigermaßen effizienten Algorithmen zur Berechnung der konvexen Hülle auf die Berechnung in zwei Dimensionen ausgelegt ist und oft auch nur für zwei Dimensionen beschrieben wird, hilft das dem Leser eher nicht weiter.

Auswahl aus dem Artikel Konvexe Hülle:

• Graham-Scan-Algorithmus mit Laufzeit ${\mathcal {O}}(n\log n)$ – funktioniert nur in 2D
• Jarvis-March (2d-Gift-Wrapping-Algorithmus) mit Laufzeit ${\mathcal {O}}(nk)$, wobei $k$ die Anzahl der Punkte auf dem Rand der Hülle ist – funktioniert auch in mehr als zwei Dimensionen, wird in den verlinkten Artikeln aber auch nur für 2D beschrieben
• QuickHull in Anlehnung an Quicksort mit erwarteter Laufzeit ${\mathcal {O}}(n\log n)$; Worstcase ${\mathcal {O}}(n^{2})$ – kenne ich nicht, ist laut Artikel auch für 3D zu gebrauchen, aber nur für 2D beschrieben
• Inkrementeller Algorithmus mit Laufzeit ${\mathcal {O}}(n\log n)$ – unverlinkt; was ist das für einer?
• Chans Algorithmus mit Laufzeit ${\mathcal {O}}(n\log k)$, wobei $k$ die Anzahl der Punkte auf dem Rand der Hülle ist. – benutzt Graham’s Scan, ist also auch nur 2D-fähig.

Da der den Algorithmus vorbereitende Abschnitt auch gleich mit „Die Berechnung eines Voronoi-Diagramms mithilfe der Delaunay-Triangulation …“ beginnt, wäre es dann nicht sinnvoller, auch einen der Algorithmus zu zitieren (bzw. zu referenzieren), die im Artikel Delaunay-Triangulierung angegeben sind? (Aber bitte nicht die letzten beiden, auf Endlos-Rekursion können wir verzichten.) Die Delaunay-Algorithmen funktionieren im Allgemeinen für beliebige Dimension (auch wenn im Artikel die Delaunay-Triangulierung nur für den $\mathbb {R} ^{2}$ definiert wird – warum eigentlich?), schon deswegen, weil Dreiecke sich immer in eine Ebene einbetten lassen. Die Dualisierung einer Delaunay-Triangulierung zum Voronoi-Diagramm ist nahezu trivial (bzw. werden Voronoi-Diagramme häufig nur durch die Triangulierung repräsentiert).

Andere Meinungen? --77.186.16.205 13:58, 31. Dez. 2017 (CET)