Line Sweep Algorithm: Computational Geometry

Key Insights

Line sweep transforms complex 2D geometric problems into manageable 1D problems by processing events in sorted order, reducing both conceptual and computational complexity.
The algorithm requires two core data structures working in tandem: an event queue (priority queue) to determine what happens next, and a status structure (balanced BST) to track what’s currently active.
Most competitive programming geometry problems—from rectangle unions to closest pairs—become straightforward once you recognize them as line sweep candidates.

Introduction to Line Sweep

Line sweep is one of those algorithmic paradigms that, once internalized, makes you see geometry problems differently. The core idea is deceptively simple: instead of reasoning about objects scattered across a 2D plane, you sweep an imaginary vertical line from left to right, processing events as you encounter them.

This mental shift is powerful. A static 2D problem becomes a dynamic 1D problem. At any moment, your sweep line intersects only a subset of objects, and you maintain this subset in a data structure that supports efficient queries and updates.

Consider finding all intersections among line segments. The naive approach checks every pair—O(n²) comparisons. But segments can only intersect if they’re “active” at the same x-coordinate. Line sweep exploits this by only comparing segments that are neighbors in the current sweep line status.

Core Components and Data Structures

Every line sweep algorithm has two essential components:

Event Queue: A priority queue containing all x-coordinates where something interesting happens. Events are processed left-to-right (smallest x first). Typical events include object starts, object ends, and intersection points.

Sweep Line Status: A balanced binary search tree (or similar ordered structure) maintaining objects currently intersected by the sweep line, ordered by their y-coordinate at the current x position.

The interaction between these structures is the algorithm’s heartbeat: pop an event, update the status, possibly discover new events to add to the queue.

from dataclasses import dataclass
from enum import Enum
from heapq import heappush, heappop
from sortedcontainers import SortedList

class EventType(Enum):
    START = 0      # Object begins
    END = 2        # Object ends
    INTERSECT = 1  # Special event (e.g., intersection)

@dataclass(order=True)
class Event:
    x: float
    event_type: EventType
    data: object  # Segment reference, point, etc.

class LineSweep:
    def __init__(self):
        self.events = []  # Min-heap by (x, event_type)
        self.status = SortedList()  # Active objects ordered by y
    
    def add_event(self, x: float, event_type: EventType, data):
        heappush(self.events, (x, event_type.value, data))
    
    def process(self):
        results = []
        while self.events:
            x, event_type_val, data = heappop(self.events)
            event_type = EventType(event_type_val)
            
            if event_type == EventType.START:
                self.handle_start(x, data, results)
            elif event_type == EventType.END:
                self.handle_end(x, data, results)
            else:
                self.handle_special(x, data, results)
        
        return results

The SortedList from the sortedcontainers library provides O(log n) insertions and deletions with O(log n) neighbor queries—exactly what we need for the status structure.

Classic Application: Line Segment Intersection

The Bentley-Ottmann algorithm is the canonical line sweep application. Given n line segments, it finds all k intersections in O((n + k) log n) time, compared to O(n²) for brute force.

The key insight: two segments can only intersect if they become adjacent in the sweep line status at some point. When we insert or remove a segment, we check for intersections with its new neighbors. When two segments swap their vertical order (at an intersection), we check their new neighbors.

from dataclasses import dataclass
from sortedcontainers import SortedList
import heapq

@dataclass
class Segment:
    x1: float
    y1: float
    x2: float
    y2: float
    id: int
    
    def y_at(self, x: float) -> float:
        """Get y-coordinate at given x."""
        if self.x1 == self.x2:
            return self.y1
        t = (x - self.x1) / (self.x2 - self.x1)
        return self.y1 + t * (self.y2 - self.y1)

def ccw(ax, ay, bx, by, cx, cy):
    """Counter-clockwise test."""
    return (cy - ay) * (bx - ax) > (by - ay) * (cx - ax)

def segments_intersect(s1: Segment, s2: Segment) -> bool:
    """Check if two segments intersect."""
    a, b = (s1.x1, s1.y1), (s1.x2, s1.y2)
    c, d = (s2.x1, s2.y1), (s2.x2, s2.y2)
    
    return (ccw(*a, *c, *d) != ccw(*b, *c, *d) and 
            ccw(*a, *b, *c) != ccw(*a, *b, *d))

def find_intersections(segments: list[Segment]) -> list[tuple[int, int]]:
    """Find all intersecting segment pairs using line sweep."""
    START, END = 0, 1
    events = []
    
    for seg in segments:
        left_x = min(seg.x1, seg.x2)
        right_x = max(seg.x1, seg.x2)
        heapq.heappush(events, (left_x, START, seg))
        heapq.heappush(events, (right_x, END, seg))
    
    current_x = float('-inf')
    # Custom key function for ordering by y at current x
    active = SortedList(key=lambda s: (s.y_at(current_x), s.id))
    intersections = []
    checked = set()
    
    def check_neighbors(seg):
        idx = active.index(seg)
        neighbors = []
        if idx > 0:
            neighbors.append(active[idx - 1])
        if idx < len(active) - 1:
            neighbors.append(active[idx + 1])
        
        for neighbor in neighbors:
            pair = tuple(sorted([seg.id, neighbor.id]))
            if pair not in checked:
                checked.add(pair)
                if segments_intersect(seg, neighbor):
                    intersections.append(pair)
    
    while events:
        current_x, event_type, seg = heapq.heappop(events)
        
        if event_type == START:
            active.add(seg)
            check_neighbors(seg)
        else:
            # Check neighbors before removal
            idx = active.index(seg)
            if 0 < idx < len(active) - 1:
                left, right = active[idx - 1], active[idx + 1]
                pair = tuple(sorted([left.id, right.id]))
                if pair not in checked:
                    checked.add(pair)
                    if segments_intersect(left, right):
                        intersections.append(pair)
            active.remove(seg)
    
    return intersections

This simplified version handles the core logic. A production implementation would also handle intersection events (where segments swap order) and degenerate cases like overlapping segments.

Interval Problems: Overlapping Rectangles

Rectangle problems are line sweep’s bread and butter. To compute the total area covered by overlapping rectangles, sweep vertically and maintain the currently covered horizontal intervals.

def rectangle_union_area(rectangles: list[tuple[int, int, int, int]]) -> int:
    """
    Calculate total area covered by rectangles.
    Each rectangle is (x1, y1, x2, y2) where (x1,y1) is bottom-left.
    """
    OPEN, CLOSE = 0, 1
    events = []
    
    for x1, y1, x2, y2 in rectangles:
        events.append((y1, OPEN, x1, x2))
        events.append((y2, CLOSE, x1, x2))
    
    events.sort()
    
    def calculate_covered_length(intervals: list[tuple[int, int]]) -> int:
        """Calculate total length covered by intervals."""
        if not intervals:
            return 0
        
        intervals.sort()
        total = 0
        current_start, current_end = intervals[0]
        
        for start, end in intervals[1:]:
            if start <= current_end:
                current_end = max(current_end, end)
            else:
                total += current_end - current_start
                current_start, current_end = start, end
        
        total += current_end - current_start
        return total
    
    active_intervals = []
    prev_y = events[0][0]
    total_area = 0
    
    for y, event_type, x1, x2 in events:
        # Add area contribution from previous y to current y
        covered_length = calculate_covered_length(active_intervals)
        total_area += covered_length * (y - prev_y)
        
        if event_type == OPEN:
            active_intervals.append((x1, x2))
        else:
            active_intervals.remove((x1, x2))
        
        prev_y = y
    
    return total_area

For better performance with many rectangles, replace the interval list with a segment tree that tracks coverage counts at each x-coordinate.

Closest Pair of Points

The closest pair problem demonstrates line sweep’s elegance. Sort points by x-coordinate, maintain a window of points within distance d (current best) of the sweep line, and use a balanced BST ordered by y-coordinate for efficient neighbor queries.

from sortedcontainers import SortedList
import math

def closest_pair(points: list[tuple[float, float]]) -> float:
    """Find minimum distance between any two points."""
    if len(points) < 2:
        return float('inf')
    
    # Sort by x-coordinate
    sorted_points = sorted(enumerate(points), key=lambda p: p[1][0])
    
    # Active points ordered by y-coordinate
    active = SortedList(key=lambda p: (p[1][1], p[0]))
    
    min_dist = float('inf')
    left = 0
    
    for right in range(len(sorted_points)):
        idx_r, (rx, ry) = sorted_points[right]
        
        # Remove points too far left
        while left < right:
            idx_l, (lx, ly) = sorted_points[left]
            if rx - lx >= min_dist:
                active.remove((idx_l, (lx, ly)))
                left += 1
            else:
                break
        
        # Check points within y-range [ry - min_dist, ry + min_dist]
        # Find insertion point and check neighbors
        for idx, (x, y) in active:
            if abs(y - ry) >= min_dist:
                continue
            dist = math.sqrt((rx - x) ** 2 + (ry - y) ** 2)
            min_dist = min(min_dist, dist)
        
        active.add((idx_r, (rx, ry)))
    
    return min_dist

The key optimization: within the active set, we only need to check points within ±d in the y-direction. With a balanced BST, we can find these candidates in O(log n) time, and there are at most O(1) such points (a geometric packing argument).

Complexity Analysis and Optimization Tips

Time Complexity Patterns:

Event processing: O(n log n) for sorting/heap operations
Status updates: O(log n) per event with balanced BST
Total: O(n log n) for most problems, O((n + k) log n) when output-sensitive

Common Pitfalls:

Floating-point precision: Use epsilon comparisons or integer arithmetic when possible. Symbolic computation libraries help for exact geometry.
Degenerate cases: Multiple events at the same x-coordinate, vertical segments, overlapping endpoints. Process events in a consistent order (e.g., starts before ends).
Status structure ordering: The comparison key must be consistent. For segments, order by y-coordinate at the current sweep line position, with tie-breaking by segment ID.

When to Use Line Sweep vs. Divide-and-Conquer:

Line sweep: when you need to process all events or when the problem has an inherently sequential nature
Divide-and-conquer: when subproblems are independent and merge is efficient (like closest pair)

Both achieve O(n log n) for closest pair, but line sweep often has simpler implementation.

Practice Problems and Extensions

Essential Practice:

The Skyline Problem (LeetCode 218): Classic sweep with height tracking
Meeting Rooms II (LeetCode 253): Minimum conference rooms needed
Rectangle Area II (LeetCode 850): Union area with coordinate compression
Perfect Rectangle (LeetCode 391): Verify exact coverage

Extensions:

3D Sweep Planes: Extend to three dimensions for problems like 3D intersection detection
Kinetic Data Structures: Handle moving objects where the sweep line status changes continuously
Rotational Sweep: Sweep by angle instead of x-coordinate for visibility problems

Line sweep is a fundamental technique that appears repeatedly in computational geometry, competitive programming, and real-world applications like GIS systems and CAD software. Master it, and a whole class of problems becomes tractable.