Bentley-Ottmann-Algorithmus Verständnisfrage

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