Shamos-Hoey Algorithm

Purpose: Decide whether any two of $n$ line segments intersect, in $O(n\log n)$ — without finding all the intersections. The original sweep-line algorithm (1976).

The Idea

Bentley-Ottmann reports all $k$ intersections in $O((n+k)\log n)$, which is $O(n^2\log n)$ when everything crosses everything. But if you only need a yes/no answer, you can stop at the first crossing — and the first crossing always involves two segments that are adjacent in the sweep-line status at some moment.

Algorithm

1. Create $2n$ events: the left and right endpoint of each segment. Sort by $x$ (ties: left endpoints first, then by $y$).
2. Maintain a status structure — a balanced BST of the segments currently crossing the sweep line, ordered by their $y$ at the sweep position.
3. Process events left to right:
   • Left endpoint of $s$: insert $s$. Test $s$ against its immediate predecessor and successor in the status. If either intersects, report yes and stop.
   • Right endpoint of $s$: before erasing $s$, test its predecessor against its successor (they become adjacent). If they intersect, report yes and stop.
4. If the sweep finishes, report no.

Code sketch

struct Seg { Point l, r; };
// comparator orders segments by their y at the current sweep x
set<Seg, SweepCmp> status;
 
bool anyIntersection(vector<Seg> segs) {
    vector<Event> ev = makeEvents(segs);
    sort(ev.begin(), ev.end());
    for (auto& e : ev) {
        if (e.isLeft) {
            auto it = status.insert(e.seg).first;
            auto nxt = next(it), prv = (it == status.begin() ? status.end() : prev(it));
            if (nxt != status.end() && intersect(*it, *nxt)) return true;
            if (prv != status.end() && intersect(*prv, *it))  return true;
        } else {
            auto it = status.find(e.seg);
            auto nxt = next(it), prv = (it == status.begin() ? status.end() : prev(it));
            if (nxt != status.end() && prv != status.end() && intersect(*prv, *nxt)) return true;
            status.erase(it);
        }
    }
    return false;
}

Complexity

• Time: $O(n\log n)$ — $2n$ events, each $O(\log n)$ BST work and $O(1)$ intersection tests
• Space: $O(n)$

Why adjacency suffices

Claim: if two segments $s$ and $t$ intersect, then at some sweep position before their leftmost intersection they are adjacent in the status order.

Consider the sweep just to the left of their first crossing point. There, $s$ and $t$ have a definite order, say $s$ below $t$; just after the crossing the order flips. The order can only change at events, so immediately before the crossing they must be neighbours — any segment strictly between them would itself have to cross one of them earlier, contradicting “first” crossing. Hence testing only adjacent pairs at every event catches the leftmost intersection. ∎

Shamos-Hoey vs Bentley-Ottmann

	Shamos-Hoey	Bentley-Ottmann
Answers	does any intersection exist	all intersections
Time	$O(n\log n)$	$O((n+k)\log n)$
Events	endpoints only	endpoints and intersection points
Status changes	insert/erase	insert/erase and swap
Code length	~50 lines	~120 lines

Variants / Use Cases

• Simple polygon testing — is a polygon self-intersecting? Feed its edges (excluding shared endpoints) to Shamos-Hoey
• Planarity of a drawing — does a given straight-line drawing have crossings?
• Validating geometric input — GIS and CAD systems run this constantly
• Sweep Line — the topic page for the general technique
• Segment Intersection — the primitive predicate