Shamos-Hoey Line segment intersection runtime

Question

In the Shamos-Hoey algorithm for finding whether or not any two of $n$ line segments intersect, which is available at this site: http://geomalgorithms.com/a09-_intersect-3.html, there is use of "nearest line above" and "nearest line below". The algorithm is supposed to run in time $O(n\log n)$. Here is their pseudocode:

Initialize event queue EQ = all segment endpoints;
Sort EQ by increasing x and y;
Initialize sweep line SL to be empty;

While (EQ is nonempty) {
    Let E = the next event from EQ;
    If (E is a left endpoint) {
        Let segE = E's segment;
        Add segE to SL;
        Let segA = the segment Above segE in SL;
        Let segB = the segment Below segE in SL;
        If (I = Intersect( segE with segA) exists) 
            return TRUE;   // an Intersect Exists
        If (I = Intersect( segE with segB) exists) 
            return TRUE;   // an Intersect Exists
    }
    Else {  // E is a right endpoint
        Let segE = E's segment;
        Let segA = the segment above segE in SL;
        Let segB = the segment below segE in SL;
        Delete segE from SL;
        If (I = Intersect( segA with segB) exists) 
            return TRUE;   // an Intersect Exists
    }
    remove E from EQ;
}
return FALSE;      // No  Intersections

If one studies the C++ code provided at the bottom of the webpage, we see that this is simply a "next" and "previous" in a BST, however, I can't seem to tell which information is being used as the BST key.

My issue is the following: if we are considering all $y$-values at the current $x$-value of the sweep line, this is not merely a check for next or previous endpoint value in a BST, and can not take $O(\log n)$ time. However, if we are checking per endpoint coordinate, this could not possibly be correct, since the following situation would lead to an incorrect execution:

The algorithm should find that $B$ and $C$ intersection on insertion of $B$ into the search tree ("SweepLine" / "SL") while sweeping. However, if we are ordering by endpoint coordinates, $A$ is $B$'s previous, $C$ is not, and this would run into problems.

Answer 1

The BST is ordered with a "above/below" relationship. The idea is that for any "event", the BST is ordered by the y-value where each line segment intersects the x-value of that "event".

When a segment is inserted or deleted, the comparisons in the BST are between the y-value of each line segment at the x-value of the current event. This can be computed with geometry in constant time given the slope of each line. The ordering only requires a single update at each event (a little subtle); the BST requires no other maintenance.

In your example, at the 2nd event when C is added, it is actually inserted above A. Then the B/C intersection would be found correctly.