A line sweep algorithm uses a conceptual line to sweep through one axis of the problem space

Previous: An algorithm is a finite set of rules that gives a sequence of operations for solving a specific type of problem

A line sweep algorithm uses a conceptual line to sweep through one axis of the problem space. Problems that can be solved with this approach can typically be boiled down to streams of events, sorted by the sweep axis (usually x or time).

The key insight is that processing events in order avoids considering all pairs or combinations naively, often reducing an O(n²) brute-force solution to O(n log n). The technique typically pairs with an “active set” — a data structure (often a balanced BST) that tracks what is currently intersected by the sweep line, updated as each event is processed.

Common applications include interval overlap detection, rectangle union area, and line segment intersection problems.