Sweep Line
Authors: Benjamin Qi, Andi Qu, Dustin Miao
Introduction to line sweep.
Prerequisites
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.
should the reader already be familiar with the 1D case (union of intervals on number line?) never explicitly mentioned in module
Resources | ||||
---|---|---|---|---|
CPH | ||||
TC |
Closest Pair
Focus Problem – read through this problem before continuing!
Solution 1
Time Complexity:
We will use a divide and conquer algorithm. First, sort the points by x-coordinate. Now, let be the subarray of points in the current step. Then, partition into two groups and representing the left and right halves of . Let and be the answer of and respectively, and define as .
Then 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 and the other is in ). Let be the x-coordinate of any median of . Define two sets and such that and
A brute force matching algorithm that computes for all , would have a worst-case runtime of (recall that and may have up to points). However, because we are searching for distances of at most , it suffices for each to check all points .
It can be shown that for each point , there is a constant number of points that satisfy this property. Because each point in is at least apart, arranging the points in the worst case would result in 6 points in the corners and sides of the bounding rectangle.
To achieve the desired complexity per layer, we need to be able to efficiently get the points sorted by both x-coordinate (for dividing ) and y-coordinate (for matching between and ). 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 steps, by the master theorem our solution now runs in .
Solution 2
(Set)
Line Segments
Focus Problem – read through this problem before continuing!
Solution
This section is not complete.
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
Old Silver | Easy | Show TagsSweep Line | |||
Old Gold | Normal | Show TagsSweep Line | |||
COI | Hard | Show TagsSweep Line | |||
CEOI | Hard | Show TagsSweep Line | |||
CEOI | Very Hard | Show TagsSweep Line | |||
Baltic OI | Very Hard | Show TagsSweep Line |
Manhattan MST
Focus Problem – read through this problem before continuing!
(KACTL code)
explanation? topcoder prob has
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CSA | Hard | 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):
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 – read through this problem before continuing!
Solution - Seeing the Boundary
Complexity:
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.
C++
#include <bits/stdc++.h>#define x first#define y secondtypedef long long ll;using namespace std;const double PI = 4 * atan(1);struct Event {short type, id;
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CEOI | Easy | Show TagsBinary Search, Radial Sweep | |||
CSES | Easy | Show Tags1DRQ, Sweep Line | |||
POI | Normal | Show TagsRadial Sweep | |||
APIO | Hard | Show TagsRadial Sweep | |||
JOI | Very Hard | Show TagsRadial Sweep |