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.
Häufig gestellte Fragen
Wann gelten zwei Polygone als benachbart?
Man unterscheidet Kanten-Nachbarschaft (gemeinsame Segmente), Punkt-Nachbarschaft (Berührung in Punkten) und lose Nachbarschaft (räumliche Nähe ohne Berührung).
Was ist die Zeitkomplexität der vorgestellten Algorithmen?
Im schlechtesten Fall (worst case) liegt sie bei O(m²), wobei m die Anzahl der Kanten/Eckpunkte ist. In der Praxis ist sie durch Optimierungen deutlich schneller.
Wie wird die Laufzeit der Algorithmen optimiert?
Durch eine Vorsortierung der Eckpunkte nach der x-Koordinate und eine effiziente Vorauswahl der Kandidaten wird ein erheblicher Speedup erreicht.
Sind die Algorithmen für moderne Prozessoren geeignet?
Ja, die Algorithmen sind hochgradig parallelisierbar, was auf Mehrkern-Systemen zu einer weiteren massiven Beschleunigung der Berechnungen führt.
Für welche Arten von Polygonen sind die Verfahren gedacht?
Sie sind speziell für planare, nicht-konvexe und sich nicht überschneidende Polygone entwickelt worden.
- 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
