Bentley-Ottmann-Algorithmus Verständnisfrage

[Namenloser]

Zitat von Blup:

Nein, in den Y-Baum (eigentlich eine Liste) fügt man Linien ein, nicht einzelne Punkte.
Beim Einfügen einer Linie vergleicht man den linken Punkt dieser Linie mit dem aktuellen Schnittpunkt der anderen Linien der Liste an dieser X-Position ("Sweep-Linie").
Dadurch wird die Einfügeposition in der Liste bestimmt.

Es kann nicht sein, dass an jedem Punkt der Schnittpunkt der Sweepline mit allen aktiven Segmenten neu berechnet wird, weil der Algorithmus dann mindestens eine Worst-Case-Komplexität von Θ(n²) hätte statt O((n+k) log n).

Nimm folgendes Szenario mit n Linien an:
scr6294_20130820.png

Der Sinn des Algorithmus ist ja aber gerade, quadratisches Laufzeitverhalten zu vermeiden.

[Blup]

Die Neuberechnung betrifft nur die Linien, mit denen tatsächlich verglichen wird.
Die Steigung jeder Linie muss man nur einmal je Linie vorberechnen.
Dann beschränkt sich die Neuberechnung auf eine Multiplikation und eine Addition.
Vergleicht man jeweils die neue Linie in der Mitte der Menge der Linien, halbiert sich die für den Vergleich relevante Menge durchschnittlich mit jedem Vergleich.
Man benötigt also ca. 8 Berechnungen und Vergleiche um eine neue Linie in eine Liste mit 256 aktiver Linien einzufügen.

[Namenloser]

Zitat von Blup:

Die Neuberechnung betrifft nur die Linien, mit denen tatsächlich verglichen wird.

Erst mal müsste man ja wissen, mit welchen Linien man überhaupt vergleichen muss, und dazu müsste man bei deiner Vorgehensweise die aktuellen Schnittpunkte aller Kandidaten mit der Sweepline kennen. Also muss man im Worstcase für bis zu O(n) Linien die Schnittpunkte mit der Sweepline neu berechnen, und das für n Linien → O(n²).

Zitat von Blup:

Die Steigung jeder Linie muss man nur einmal je Linie vorberechnen.
Dann beschränkt sich die Neuberechnung auf eine Multiplikation und eine Addition.

Ist für die asymptotische Laufzeitkomplexität egal.

Ich bin mir zu 95% sicher, dass das, was ich gestern geschrieben habe, stimmt. Ich habe es mehrfach auf dem dem Papier durchgespielt und es hat in allen Fällen funktioniert, und es passt auch zu den Beschreibungen des Bentley-Ottman-Algorithmus. Deine Vorgehensweise taucht dagegen in keiner Beschreibung auf. Sie würde zwar auch funktionieren (auf Kosten einer schlechteren Laufzeitkomplexität), aber der Bentley-Ottman-Algorithmus geht nun mal anders.

Trotzdem Danke fürs Mitdenken!

[Blup]

Zitat von NamenLozer:

Erst mal müsste man ja wissen, mit welchen Linien man überhaupt vergleichen muss, und dazu müsste man bei deiner Vorgehensweise die aktuellen Schnittpunkte aller Kandidaten mit der Sweepline kennen.

Muss man nicht, man kennt aus der Reihenfolge in der Y-Liste in welcher Reihenfolge von Oben nach Unten die Linien durch die Sweep-Linie geschnitten werden.

So wie ich die Beschreibungen verstanden habe ist bei der Y-Liste nie von Punkten die Rede.
Der Algo sieht vor das Linien eingefügt, innerhalb der Liste getauscht oder entfernt werden.

In der X-Liste werden allerdings tatsächlich Punkte eingefügt.
Punkte an denen Linien beginnen oder enden und die Schnittpunkte.

Bin mal gespannt auf deine Implementation.