Sweep für Sichtbarkeitsgraphen < Algorithm. Geometrie < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo zusammen!
Ich habe ein Problem, mir folgendes vorzustellen:
Ich habe Liniensegmente in der Ebene gegeben, und mache nun folgendes:
Für jeden Endpunkt p: (also das sind die Endpunkte der Linien)
- sortiere alle Endpunkte rechts von p nach Winkeln von p
- drehe einen Strahl S von p gegen den Uhrzeigersinn von Süd nach Nord:
- führe in balanciertem Baum sortiert nach Abstand von p Buch darüber, welche Segmente von S gerade geschnitten werden.
- sei q der Schnittpunkt von S mit dem zu p nächsten Liniensegment auf S. Falls [mm] q\in [/mm] V, berichte Sichtbarketiskante [mm] \overline{pq}
[/mm]
Das ganz ist übrigens ein Sweep zur Berechnung des Sichtbarkeitsgraphen, falls das jemandem hilft.
Wie muss ich mir diesen balancierten Baum vorstellen? Also, was allgemein ein balancierter Baum ist, weiß ich. Aber was wird da hier wie eingefügt? Und wonach ist das sortiert? Nach dem Abstand von p wahrscheinlich, oder?
Und vielleicht kann mir noch jemand sagen, wie ich auf die Laufzeit [mm] $O(n\log [/mm] n)$ für ein festes p komme?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 So 30.07.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
