Bentley-Ottmann-Algorithmus Verständnisfrage

[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!