Sweep Line

Authors: Benjamin Qi, Andi Qu, Dustin Miao, Timothy Gao, Mihnea Brebenel

Introduction to line sweep.

Imagine you have a vertical line that "sweeps" the plane from left to right. That's the main idea behind the sweep line.

You might be thinking "wait - isn't keeping track of the sweep line at all possible positions super inefficient?" And you'd be correct. However, we don't actually need to keep track of the sweep line at all possible positions - only at the "critical" positions (e.g. points and intersections).

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

should the reader already be familiar with the 1D case (union of intervals on number line?) never explicitly mentioned in module

Closest Pair

Focus Problem – try your best to solve this problem before continuing!

Solution 1

Time Complexity: O(nlogn)\mathcal{O}(n\log n)

We will use a divide and conquer algorithm. First, sort the points by x-coordinate. Now, let PP be the subarray of points in the current step. Then, partition PP into two groups LL and RR representing the left and right halves of PP. Let δl\delta_l and δr\delta_r be the answer of LL and RR respectively, and define δ\delta as min(δl,δr)\min(\delta_l, \delta_r).

Then δ\delta is the upperbound of the answer. If a more optimal answer exists, it must bridge the two halves of the array (i.e. one of its endpoints is in LL and the other is in RR). Let mxmx be the x-coordinate of any median of PP. Define two sets LL' and RR' such that L={piximx,mxxiδ}L' = \{p_i | x_i \leq mx, mx - x_i \leq \delta\} and R={piximx,ximxδ}R' = \{p_i | x_i \geq mx, x_i - mx \leq \delta\}

A brute force matching algorithm that computes dist(p,q)\texttt{dist}(p, q) for all pLp \in L', qRq \in R' would have a worst-case runtime of (n2)2=O(n2)(\frac n 2)^2 = \mathcal{O}(n^2) (recall that LL' and RR' may have up to N2\frac N 2 points). However, because we are searching for distances of at most δ\delta, it suffices for each pLp \in L' to check all points {qqR,p.yδq.yp.y+δ}\{q | q \in R', p.y - \delta \leq q.y \leq p.y + \delta\}.

It can be shown that for each point pp, there is a constant number of points that satisfy this property. Because each point in RR' is at least δrδ\delta_r \geq \delta apart, arranging the points in the worst case would result in 6 points in the corners and sides of the bounding rectangle.

Worst-case bounding box arrangement

To achieve the desired O(n)\mathcal{O}(n) complexity per layer, we need to be able to efficiently get the points sorted by both x-coordinate (for dividing PP) and y-coordinate (for matching between LL' and RR'). This can be achieved by taking advantage of the merge-sort-like algorithm: sort by x-coordinate in the beginning, then for each step, merge the y-coordinates recursively.

Because each step now runs in linear time and there is a total of logn\lceil \log n \rceil steps, by the master theorem our solution now runs in O(nlogn)\mathcal{O}(n\log n).


#include <bits/stdc++.h>
using namespace std;
struct Point {
long double x, y;
bool operator<(const Point &other) {
if (x == other.x) { return y < other.y; }
return x < other.x;

Solution 2

Time Complexity: O(nlogn)\mathcal{O}(n\log n)

Extending Solution 1, we can use a set instead of divide and conquer. Once again, we define δ\delta as the shortest distance between two points so far. After sorting the points by x-coordinate, we iterate through them while maintaining a running window containing the y-coordinates of all points in [xδ,x][x-\delta,x].

Set Solution Sweep Line Bounding Box

As we visit point PP, we utilize the set to consider all points with y-coordiate in [Pyδ,Py+δ][P_y-\delta, P_y+\delta]. The set contains [Pxδ,Px][P_x-\delta, P_x] because of how it is maintained as a running window. Now we have the same bounding box as Solution 1, with at most 6 points inside.

For each point, we recalculate δ=min(δ,δp)\delta = \min(\delta, \delta_p), and update our set accordingly. Each point is inserted and removed from the set at most once, so the algorithm yields O(nlogn)\mathcal{O}(n\log n).

Line Segments

Focus Problem – try your best to solve this problem before continuing!


Let's simplify the problem a little bit and focus on finding any overlapping segments.

To find a pair of overlapping segments, use a sweep line approach by sweeping a vertical line across the scene from left to right, pausing at every segment endpoint.

We simulate this by sorting all the segment endpoints by xx and walking through the sorted array (called 'events' in the code below). As we scan, we keep track of active segments using a set (called 'active_segments' in the code below). When we hit the beginning point of a segment, add it to the active set, and remove it from the active set when we hit the ending point of a segment.

Inserting or removing the active segments from the set takes O(logn)\mathcal{O}(\log n) per operation.

The active set of segments is ordered by yy coordinate. If two segments overlap, they are adjacent in the set, so every time we insert or remove a segment, we check if the adjacent segments overlap.

Here is an animation of how it works:


Time complexity: O(nlogn)\mathcal{O}(n\log n).


#include <bits/stdc++.h>
using namespace std;
long long sweep_line_x;
Code Snippet: Point Structure (Click to expand)
Code Snippet: Segment Structure (Click to expand)


StatusSourceProblem NameDifficultyTags
Old SilverEasy
Show TagsSweep Line
Old GoldNormal
Show TagsSweep Line
Show TagsSweep Line
Show TagsSweep Line
CEOIVery Hard
Show TagsSweep Line
Baltic OIVery Hard
Show TagsSweep Line

Manhattan MST

Focus Problem – try your best to solve this problem before continuing!

The key observation is that although there are many points, they're spread across a pretty small surface. Because of this, instead of using Kruskal's or Prim's algorithm, we can use Dijkstra's. Starting from an arbitrary point, we run Dijkstra's algorithm with a priority queue that will sort the points by their distance to the MST.

Time Complexity: O(S3logS)\mathcal{O}(S^3\log S), where S is the grid size


#include <bits/stdc++.h>
using namespace std;
const int GRID_SZ = 1000;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
int main() {
int n;
cin >> n;
StatusSourceProblem NameDifficultyTags
Show TagsManhattan MST

Radial Sweep

Instead of a vertical line sweeping the plane from left to right, radial sweep involves a ray that rotates around a central point (like a radar screen):

Radar screen gif

In this case, we sort points/events by their bearing instead of by their x- and y-coordinates. Besides that, the mechanics are the same as those of normal line sweep.

Focus Problem – try your best to solve this problem before continuing!

Solution - Seeing the Boundary

Complexity: O(N+RpilogR)\mathcal O(N + Rp_i \log R)

In this problem, there are three types of events: when our ray hits a fence post, enters a rock, or exits a rock.

The second and third types of events can be found for each rock by sorting the rays to its vertices by bearing and then taking the two endpoints of the sorted list. These two rays are the two tangents to the rock.

We can then perform a radial sweep to find the fence posts that Farmer Don can see - these fence posts are simply the ones where the number of type-2 and type-3 events we've processed so far are equal.

Note that some optimizations (e.g. not constructing the list of fence posts explicitly) may be required to get 100 points.


#include <bits/stdc++.h>
#define x first
#define y second
typedef long long ll;
using namespace std;
const double PI = 4 * atan(1);
struct Event {
short type, id;


StatusSourceProblem NameDifficultyTags
Show TagsBinary Search, Radial Sweep
Show Tags1DRQ, Sweep Line
Show TagsRadial Sweep
Show TagsRadial Sweep
JOIVery Hard
Show TagsRadial Sweep

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!