Nächste Seite:
Inhalt
Inhalt
F
ACHBEREICH
I
NFORMATIK
L
EHRGEBIET
P
RAKTISCHE
I
NFORMATIK
VI
Diplomarbeit
Schwerpunkt-Voronoi-Diagramme
(Centroidal Voronoi Diagrams/Tesselations)
Christian Raskob, fun . raskob.de
28. Juni 2004
Betreuer:
Dr. Christian Icking und
Dr. Lihong Ma
Inhalt
Abbildungsverzeichnis
Einleitung
Überblick
Abgrenzung zum Voronoi-Diagramm
Mathematische Grundlagen
Abstandsbegriffe
Dichtefunktion
Inhalt
Schwerpunkt
Kompaktheit
Grundmenge
Voronoi-Diagramm
Delaunay-Zerlegung
Definition und Eigenschaften
Definition
Beispiele
Im Eindimensionalen
In der Ebene
In höheren Dimensionen
Grundmenge
Abgeschlossenheit
Beschränktheit
Metrische Probleme
Minimalität
Minimalität des Schwerpunkt-Voronoi-Diagramms
Existenz einer Minimalkonfiguration
Anzahl und Lage von Voronoi-Punkten
Weitere Eigenschaften
Nichteindeutigkeit
Fixpunkte
Asymptotisch optimale Schwerpunkt-Voronoi-Diagramme
Diskrete Grundmenge
Anwendungen
Optimale Verteilung von Ressourcen
Datenreduktion in Bildern
Quantisierung
Erzeugung hochwertiger Gitter
Weitere Anwendungen
Algorithmen
Einschränkungen
Berechnung des Voronoi-Diagramms
Algorithmen
Laufzeitschranke
Schwerpunktberechnung
Schwerpunkt eines einfachen und zusammenhängenden Polygons
Algorithmus
Schwerpunkt in nicht einfachen oder nicht zusammenhängenden Polygonen
Laufzeit
Andere Verfahren
Polygonschnitt
Algorithmus
Laufzeit
Nächste Punkte
Element-Test in Polygonen
Erzeugung von Zufallspunkten
Zufallspunkte im Eindimensionalen
Zufallspunkte in der Ebene
Maximale Dichte
Laufzeit
Berechnung
Lloyd-Algorithmus
Algorithmus
Konvergenz
Minimalität
Terminierung
Laufzeit
Verbesserungen
Erweiterungen
k
-Means-Algorithmus
Algorithmus
Konvergenz
Minimalität
Terminierung
Laufzeit
Verbesserungen
Erweiterungen
Andere Algorithmen
Abschließende Bemerkungen
CentroidalVoronoi
Algorithmen
Dichtefunktionen
Integrierte Dichtefunktionen
Externe Dichtefunktionen
Rechengenauigkeit
Quelltext und Übersetzung
Bedienung
Symbolleiste
Informationsbereich
Darstellung Schwerpunkt-Voronoi-Diagramm
Weitere Schwerpunkt-Voronoi-Diagramme
Konstante Dichte
Nicht konstante Dichte
Andere Dichte
Literatur
Über dieses Dokument ...
Christian Raskob 2004-06-22