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  IntersectionsIf 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.
Shamos-Hoey Line segment intersection runtime
algorithms;algorithm analysis