Zwei Polygone sind benachbart wenn sie gemeinsame Kantensegmente teilen („Kanten-
Nachbarschaft“) oder wenn sie gemeinsame Punkte auf einer Kante besitzen („Punkt-
Nachbarschaft“) oder wenn sie sich gar nicht berühren, sondern in einer gewissen Nähe zueinander liegen („lose Nachbarschaft“). Die vorliegende Arbeit beschäftigt sich mit
Verfahren zur Auffindung dieser drei Arten von Nachbarschaftsbeziehungen in Mengen
von planaren, nicht-konvexen sich nicht-überschneidenden Polygonen. Nach der Vorstellung
eines bereits bekannten Algorithmus zur „Kanten-Nachbarschaft“-Suche werden im
Hauptteil der Arbeit die beiden Algorithmen zur Auffindung der „Punkt-Nachbarschaft“
und der „losen Nachbarschaft“ entwickelt. Im worst case liegt die Zeitkomplexität dieser
beiden Algorithmen in O(m²) (wobei m die Gesamtanzahl aller Kanten bzw. Eckpunkte
ist). Eine Sortierung aller Eckpunkte nach der x-Koordinate und eine anschließende, effiziente Vorauswahl führen in der Praxis jedoch zu einem vielfachen Speedup der
Laufzeiten (im Vergleich zu einer rein quadratischen Zeitkomplexität). Durch die Tatsache,
dass die beiden Algorithmen hochgradig parallelisierbar sind, kann ein weiterer
Speedup erreicht werden. Diese Möglichkeit wird zum Schluss der Arbeit diskutiert.
Inhaltsverzeichnis
- Einleitung
- Grundlagen
- Definitionen
- Verwendete Formelzeichen
- Stand der Technik
- Algorithmus: Kanten-Nachbarschaft
- Algorithmen
- Überlegungen zur Darstellung von Geraden
- Algorithmus 1: Punkt-Nachbarschaft
- Algorithmus 2: Lose Nachbarschaft
- Alternative Auffasungen der losen Nachbarschaft
- Untersuchungen zur Parallelisierbarkeit
- Parallelisierung des Hauptteils
- Parallelisierung der Vorausberechnung
- Bewertung und Vergleich
- Benchmarks
- Auswertung
Zielsetzung und Themenschwerpunkte
Diese Arbeit befasst sich mit der Entwicklung von Verfahren zur Auffindung von Nachbarschaftsbeziehungen in Mengen von planaren, nicht-konvexen und sich nicht-überschneidenden Polygonen. Dabei werden drei Arten von Nachbarschaftsbeziehungen definiert: Kanten-Nachbarschaft, Punkt-Nachbarschaft und lose Nachbarschaft.
- Entwicklung effizienter Algorithmen zur Bestimmung von Punkt- und losen Nachbarschaften
- Analyse der Zeitkomplexität der entwickelten Algorithmen
- Untersuchung der Parallelisierbarkeit der Algorithmen
- Bewertung und Vergleich der Algorithmen anhand von Benchmarks
- Diskussion der Anwendungsmöglichkeiten der entwickelten Verfahren
Zusammenfassung der Kapitel
- Kapitel 1: Einleitung: Einleitung in das Thema der Nachbarschaftssuche in Mengen von Polygonen. Vorstellung der Problematik und der Zielsetzung der Arbeit.
- Kapitel 2: Grundlagen: Definition wichtiger Begriffe und Formelzeichen, die im weiteren Verlauf der Arbeit verwendet werden.
- Kapitel 3: Stand der Technik: Vorstellung eines bereits bekannten Algorithmus zur Suche nach Kanten-Nachbarschaften.
- Kapitel 4: Algorithmen: Entwicklung der Algorithmen zur Bestimmung von Punkt- und losen Nachbarschaften. Analyse der Zeitkomplexität und Beschreibung der Funktionsweise der Algorithmen.
- Kapitel 5: Untersuchungen zur Parallelisierbarkeit: Diskussion der Möglichkeiten zur Parallelisierung der entwickelten Algorithmen. Analyse der Parallelisierungspotenziale und der Herausforderungen.
- Kapitel 6: Bewertung und Vergleich: Durchführung von Benchmarks zur Evaluation der Performance der Algorithmen. Auswertung der Ergebnisse und Vergleich der Algorithmen.
Schlüsselwörter
Nachbarschaftssuche, planare Polygone, nicht-konvex, nicht-überschneidende, Kanten-Nachbarschaft, Punkt-Nachbarschaft, lose Nachbarschaft, Algorithmen, Zeitkomplexität, Parallelisierung, Benchmarks.
- Quote paper
- Konstantin Sokolov (Author), 2010, Nachbarschaftssuche in Mengen von planaren, nicht-konvexen, nicht-überschneidenden Polygonen, Munich, GRIN Verlag, https://www.grin.com/document/146775
