Nachbarschaftssuche in Mengen von planaren, nicht-konvexen, nicht-überschneidenden Polygonen
Seiten
2010
|
10003 A. 3. Auflage
GRIN Verlag
978-3-640-57710-1 (ISBN)
GRIN Verlag
978-3-640-57710-1 (ISBN)
- Titel nicht im Sortiment
- Artikel merken
Studienarbeit aus dem Jahr 2010 im Fachbereich Informatik - Allgemeines, Rheinisch-Westfälische Technische Hochschule Aachen (Mensch-Maschine-Interaktion), Sprache: Deutsch, Abstract: 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.
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.
| Erscheint lt. Verlag | 28.3.2010 |
|---|---|
| Sprache | deutsch |
| Maße | 148 x 210 mm |
| Gewicht | 77 g |
| Themenwelt | Mathematik / Informatik ► Informatik |
| Schlagworte | Adjazenz • konkav • konvex • Nachbarschaft • Nachbarschaftssuche • Polygone |
| ISBN-10 | 3-640-57710-8 / 3640577108 |
| ISBN-13 | 978-3-640-57710-1 / 9783640577101 |
| Zustand | Neuware |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
das Praxishandbuch
Buch | Hardcover (2024)
Markt + Technik Verlag
CHF 27,90
Buch | Softcover (2024)
BILDNER Verlag
CHF 55,85
den digitalen Office-Notizblock effizient nutzen für PC, Tablet und …
Buch | Softcover (2023)
Markt + Technik Verlag
CHF 13,90
