1
$\begingroup$

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:

Counterexample

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.