Studienarbeit aus dem Jahr 2010 im Fachbereich Informatik - Allgemeines, Rheinisch-Westfalische 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 beruhren, sondern in einer gewissen Nahe zueinander liegen ( lose Nachbarschaft"). Die vorliegende Arbeit beschaftigt sich mit Verfahren zur Auffindung dieser drei Arten von Nachbarschaftsbeziehungen in Mengen von planaren, nicht-konvexen sich nicht-uberschneidenden 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 Zeitkomplexitat 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 anschliessende, effiziente Vorauswahl fuhren in der Praxis jedoch zu einem vielfachen Speedup der Laufzeiten (im Vergleich zu einer rein quadratischen Zeitkomplexitat). Durch die Tatsache, dass die beiden Algorithmen hochgradig parallelisierbar sind, kann ein weiterer Speedup erreicht werden. Diese Moglichkeit wird zum Schluss der Arbeit diskutiert