Plane Sweep Algorithm
Aritra Banik1
Assistant Professor
National Institute of Science Education and Research
1
Slide ideas borrowed from Marc van Kreveld and Subhash Suri
Plane Sweep Algorithm 1/27
Intersection Detection
Determine pairs of intersecting objects?
Collision detection in robotics and motion planning.
Visibility, occlusion, rendering in graphics.
Map overlay in GISs: e.g. road networks on county maps.
Plane Sweep Algorithm 2/27
Line Segment Intersection
Let’s first look at the easiest version of the problem:
Given a set of of n line segments in the plane, find all
intersection points efficiently
Naive algorithm?
Plane Sweep Algorithm 3/27
Line Segment Intersection
Let’s first look at the easiest version of the problem:
Given a set of of n line segments in the plane, find all
intersection points efficiently
Naive algorithm?Check all pairs. O(n2 ).
Plane Sweep Algorithm 3/27
Line Segment Intersection
Algorithm 1 FindIntersections(S)
Input: A set S of line segments in the plane.
Output: The set of intersection points among the segments in S.
1: for each pair of line segments ei , ej ∈ S do
2: if ei and ej intersect then
3: report their intersection point
4: end if
5: end for
Plane Sweep Algorithm 4/27
Line Segment Intersection
Algorithm 2 FindIntersections(S)
Input: A set S of line segments in the plane.
Output: The set of intersection points among the segments in S.
1: for each pair of line segments ei , ej ∈ S do
2: if ei and ej intersect then
3: report their intersection point
4: end if
5: end for
Question: Why can we say that this algorithm is optimal?
Plane Sweep Algorithm 4/27
Line Segment Intersection
Plane Sweep Algorithm 5/27
Line Segment Intersection
The asymptotic running time of an algorithm is always
input-sensitive (depends on n)
Plane Sweep Algorithm 5/27
Line Segment Intersection
The asymptotic running time of an algorithm is always
input-sensitive (depends on n)
Plane Sweep Algorithm 5/27
Line Segment Intersection
The asymptotic running time of an algorithm is always
input-sensitive (depends on n)
We may also want the running time to be output-sensitive: if
the output is large, it is fine to spend a lot of time, but if the
output is small, we want a fast algorithm
Plane Sweep Algorithm 5/27
Line Segment Intersection
The asymptotic running time of an algorithm is always
input-sensitive (depends on n)
We may also want the running time to be output-sensitive: if
the output is large, it is fine to spend a lot of time, but if the
output is small, we want a fast algorithm
If there are k intersections, then ideal will be O(n log n + k)
time.
Plane Sweep Algorithm 5/27
Line Segment Intersection
The asymptotic running time of an algorithm is always
input-sensitive (depends on n)
We may also want the running time to be output-sensitive: if
the output is large, it is fine to spend a lot of time, but if the
output is small, we want a fast algorithm
If there are k intersections, then ideal will be O(n log n + k)
time.
We will describe a O((n + k)logn) solution. Also introduce a
new technique : plane sweep.
Plane Sweep Algorithm 5/27
An Easier Problem:
s1 s4 s6
s3
s2 s5
Given a set of intervals on the real line, find all overlapping
pairs.
Plane Sweep Algorithm 6/27
An Easier Problem:
s1 s4 s6
s3
s2 s5
Given a set of intervals on the real line, find all overlapping
pairs.
Imagine a horizontal line passing over the plane from top to
bottom, solving the problem as it moves
Plane Sweep Algorithm 6/27
An Easier Problem:
s1 s4 s6
s3
s2 s5
Given a set of intervals on the real line, find all overlapping
pairs.
Imagine a horizontal line passing over the plane from top to
bottom, solving the problem as it moves
The sweep line stops and the algorithm computes at certain
positions : events/ event points
Plane Sweep Algorithm 6/27
An Easier Problem:
s1 s4 s6
s3
s2 s5
Given a set of intervals on the real line, find all overlapping
pairs.
Imagine a horizontal line passing over the plane from top to
bottom, solving the problem as it moves
The sweep line stops and the algorithm computes at certain
positions : events/ event points
The algorithm stores the relevant situation at the current
position of the sweep line : status
Plane Sweep Algorithm 6/27
An Easier Problem:
s1 s4 s6
s3
s2 s5
Given a set of intervals on the real line, find all overlapping
pairs.
Imagine a horizontal line passing over the plane from top to
bottom, solving the problem as it moves
The sweep line stops and the algorithm computes at certain
positions : events/ event points
The algorithm stores the relevant situation at the current
position of the sweep line : status
The algorithm knows everything it needs to know before the
sweep line, and found all intersection pairs.
Plane Sweep Algorithm 6/27
An Easier Problem:
s1 s4 s6
s3
s2 s5
Sort the endpoints and handle them from left to right;
maintain currently intersected intervals in a balanced search
tree T
Plane Sweep Algorithm 7/27
An Easier Problem:
s1 s4 s6
s3
s2 s5
Sort the endpoints and handle them from left to right;
maintain currently intersected intervals in a balanced search
tree T
Left endpoint of si : for each sj in T , report the pair (si , sj ).
Then insert si in T
Right endpoint of si : delete si from T
Plane Sweep Algorithm 7/27
An Easier Problem:
s1 s4 s6
s3
s2 s5
Sort the endpoints and handle them from left to right;
maintain currently intersected intervals in a balanced search
tree T
Left endpoint of si : for each sj in T , report the pair (si , sj ).
Then insert si in T
Right endpoint of si : delete si from T
There will be 2n many event points.
Plane Sweep Algorithm 7/27
An Easier Problem:
s1 s4 s6
s3
s2 s5
Sort the endpoints and handle them from left to right;
maintain currently intersected intervals in a balanced search
tree T
Left endpoint of si : for each sj in T , report the pair (si , sj ).
Then insert si in T
Right endpoint of si : delete si from T
There will be 2n many event points.
At each event point we do two operations
Insert/Delete
Report intersection
Plane Sweep Algorithm 7/27
An Easier Problem:
s1 s4 s6
s3
s2 s5
Sort the endpoints and handle them from left to right;
maintain currently intersected intervals in a balanced search
tree T
Left endpoint of si : for each sj in T , report the pair (si , sj ).
Then insert si in T
Right endpoint of si : delete si from T
There will be 2n many event points.
At each event point we do two operations
Insert/Delete
Report intersection
Total time = Total insert delete time + Total time to report
intersection
Plane Sweep Algorithm 7/27
An Easier Problem:
s1 s4 s6
s3
s2 s5
Sort the endpoints and handle them from left to right;
maintain currently intersected intervals in a balanced search
tree T
Left endpoint of si : for each sj in T , report the pair (si , sj ).
Then insert si in T
Right endpoint of si : delete si from T
There will be 2n many event points.
At each event point we do two operations
Insert/Delete
Report intersection
Total time = Total insert delete time + Total time to report
intersection
2n ∗ log n + k
Plane Sweep Algorithm 7/27
Back to 2D Problem
`1 `4 `5 `6
`3
`2
Plane Sweep Algorithm 8/27
Back to 2D Problem
`1 `4 `5 `6
`3
`2
Imagine a horizontal line passing over the plane from top to
bottom, solving the problem as it moves
Question: What are the event points?
Plane Sweep Algorithm 8/27
Back to 2D Problem
`1 `4 `5 `6
`3
`2
Imagine a horizontal line passing over the plane from top to
bottom, solving the problem as it moves
Question: What are the event points?
Maintain vertical order of segments intersecting the sweep line;
Plane Sweep Algorithm 8/27
Back to 2D Problem
`1 `4 `5 `6
`3
`2
Insert `1 , add the end point of `1 to the event queue
Plane Sweep Algorithm 9/27
Back to 2D Problem
`1 `4 `5 `6
`3
`2
Insert `1 , add the end point of `1 to the event queue
Insert `2 , Current order `1 , `2
Plane Sweep Algorithm 9/27
Back to 2D Problem
`1 `4 `5 `6
`3
`2
Insert `1 , add the end point of `1 to the event queue
Insert `2 , Current order `1 , `2
Insert `3 , Current order `1 , `3 , `2 ,
Check whether `3 intersects with `1 or `2 .
Insert intersection point of `2 and `3 into the event queue.
Plane Sweep Algorithm 9/27
Back to 2D Problem
`1 `4 `5 `6
`3
`2
Insert `1 , add the end point of `1 to the event queue
Insert `2 , Current order `1 , `2
Insert `3 , Current order `1 , `3 , `2 ,
Check whether `3 intersects with `1 or `2 .
Insert intersection point of `2 and `3 into the event queue.
Current order `1 , `2 , `3 , insert intersection point of `3 , `2 to the
event queue.
Plane Sweep Algorithm 9/27
Back to 2D Problem
`1 `4 `5 `6
`3
`2
Insert `1 , add the end point of `1 to the event queue
Insert `2 , Current order `1 , `2
Insert `3 , Current order `1 , `3 , `2 ,
Check whether `3 intersects with `1 or `2 .
Insert intersection point of `2 and `3 into the event queue.
Current order `1 , `2 , `3 , insert intersection point of `3 , `2 to the
event queue.
. . . and so on . . .
Plane Sweep Algorithm 9/27
Events
When do the events happen? When the sweep line is at
a left endpoint of a line segment
a right endpoint of a line segment
an intersection point of a line segment
Plane Sweep Algorithm 10/27
A left endpoint of a line segment
`1 We use a balanced binary search
tree with the line segments in the
`4 `6 leaves as the status structure.
Search and insert.
`3
`2
`5
Plane Sweep Algorithm 11/27
A left endpoint of a line segment
`1 We use a balanced binary search
tree with the line segments in the
`4 `6 leaves as the status structure.
Search and insert.
`3
Should we find out intersection of
`2 `6
`5
Plane Sweep Algorithm 11/27
A left endpoint of a line segment
`1 We use a balanced binary search
tree with the line segments in the
`4 `6 leaves as the status structure.
Search and insert.
`3
Should we find out intersection of
`2 `6
`5 At the time of insert `6 is adjacent
to `4 and l3 .
Plane Sweep Algorithm 11/27
A left endpoint of a line segment
`1 We use a balanced binary search
tree with the line segments in the
`4 `6 leaves as the status structure.
Search and insert.
`3
Should we find out intersection of
`2 `6
`5 At the time of insert `6 is adjacent
to `4 and l3 .
Check whether `6 intersects with `4
and l3 or not, if intersects, insert
the intersection points in the event
queue.
Plane Sweep Algorithm 11/27
A left endpoint of a line segment
`1 We use a balanced binary search
tree with the line segments in the
`4 `6 leaves as the status structure.
Search and insert.
`3
Should we find out intersection of
`2 `6
`5 At the time of insert `6 is adjacent
to `4 and l3 .
Check whether `6 intersects with `4
and l3 or not, if intersects, insert
the intersection points in the event
queue.
Plane Sweep Algorithm 11/27
A right endpoint of a line segment
`1 Sweep line reaches right endpoint
`4 of a line segment: delete the line
`6 segment
`3
`2
`5
Plane Sweep Algorithm 12/27
A right endpoint of a line segment
`1 Sweep line reaches right endpoint
`4 of a line segment: delete the line
`6 segment
`3 After deletion of `6 , `3 and `4
becomes adjacent.
`2
If `3 and `4 intersects insert the
`5 intersection point into the event
queue.
Plane Sweep Algorithm 12/27
Sweep line reaches an intersection point
Sweep line reaches an intersection point
`1 of `i and `j
`4
Exchange `i and `j in the order list.
`i
`j
`3
`2
Plane Sweep Algorithm 13/27
Sweep line reaches an intersection point
Sweep line reaches an intersection point
`1 of `i and `j
`4
Exchange `i and `j in the order list.
`i
If `i and its new left neighbor
`j intersects, then insert this
`3 intersection point in the event
queue
`2 If `j and its new left neighbor
intersects, then insert this
intersection point in the event
queue.
Plane Sweep Algorithm 13/27
Sweep line reaches an intersection point
Sweep line reaches an intersection point
`1 of `i and `j
`4
Exchange `i and `j in the order list.
`i
If `i and its new left neighbor
`j intersects, then insert this
`3 intersection point in the event
queue
`2 If `j and its new left neighbor
intersects, then insert this
intersection point in the event
queue.
Report the intersection point.
Plane Sweep Algorithm 13/27
Finding events
Before the sweep algorithm starts, we know all upper endpoint
events and all lower endpoint events
But: How do we know intersection point events??? (those we
were trying to find . . .)
Observe: Two line segments can only intersect if they are
horizontal neighbors
Plane Sweep Algorithm 14/27
Runtime
At each event constant many updates
Plane Sweep Algorithm 15/27
Runtime
At each event constant many updates
Since both the event queue and T are balanced binary search
trees, handling an event takes only O(log n) time.
Plane Sweep Algorithm 15/27
Runtime
At each event constant many updates
Since both the event queue and T are balanced binary search
trees, handling an event takes only O(log n) time.
Total no of events are O(n + k).
The algorithm takes O(n log n + k log n) time If k = O(n),
then this is O(n log n)
Plane Sweep Algorithm 15/27
Runtime
At each event constant many updates
Since both the event queue and T are balanced binary search
trees, handling an event takes only O(log n) time.
Total no of events are O(n + k).
The algorithm takes O(n log n + k log n) time If k = O(n),
then this is O(n log n)
Note that if k is really large, the brute force O(n2 ) time
algorithm is more efficient
Plane Sweep Algorithm 15/27
Area of Union of rectangles
Given a layout in which objects are orthogonal polygons with
sides parallel to the axises. The task is to find the area covered
by all the objects.
Plane Sweep Algorithm 16/27
Area of Union of rectangles
Given a layout in which objects are orthogonal polygons with
sides parallel to the axises. The task is to find the area covered
by all the objects.
plane sweep: Keep track of the area that being sweeped.
Plane Sweep Algorithm 16/27
Area of Union of rectangles
Given a layout in which objects are orthogonal polygons with
sides parallel to the axises. The task is to find the area covered
by all the objects.
plane sweep: Keep track of the area that being sweeped.
event points: When is the intersection of the the
rectangels with the sweep line changes?
Plane Sweep Algorithm 16/27
Area of Union of rectangles
Given a layout in which objects are orthogonal polygons with
sides parallel to the axises. The task is to find the area covered
by all the objects.
plane sweep: Keep track of the area that being sweeped.
event points: When is the intersection of the the
rectangels with the sweep line changes?Left and right end
point of the rectangeles.
What is the area between any two event points?
Plane Sweep Algorithm 16/27
Area of Union of rectangles
δx
Given a layout in which objects are orthogonal polygons with
sides parallel to the axises. The task is to find the area covered
by all the objects.
plane sweep: Keep track of the area that being sweeped.
event points: When is the intersection of the the
rectangels with the sweep line changes?Left and right end
point of the rectangeles.
What is the area between any two event points?
δx × y where y is the length of the intersection of the the
rectangels with the sweep line.
Plane Sweep Algorithm 16/27
Area of Union of rectangles
δx
Intersection of the the rectangels with the sweep line is a set
of intervals.
Thus the problem at hand becomes to maintain the intercepts.
The y can change only at
The beginning of a rectangle.
The end of the rectangle.
Plane Sweep Algorithm 17/27
Sum of the union of the intervals
Naïve Method:
Plane Sweep Algorithm 18/27
Sum of the union of the intervals
Naïve Method:
At each event point find out y by a sweepline method.
event points: Left and right end point of an interval.
status: Balanced binary search tree to store intervals.
At each event point if tree is not empty sum+= distance
between current and last event point.
Plane Sweep Algorithm 18/27
Sum of the union of the intervals
δx
Naïve Method:
At each event point find out y by a sweepline method.
event points: Left and right end point of an interval.
status: Balanced binary search tree to store intervals.
At each event point if tree is not empty sum+= distance
between current and last event point.
Complexity of sum of intervals O(n log n)
Complexity of area of union of rectangles O(n2 log n)
Plane Sweep Algorithm 18/27
Sum of the union of the intervals
δx
Naïve Method:
At each event point find out y by a sweepline method.
event points: Left and right end point of an interval.
status: Balanced binary search tree to store intervals.
At each event point if tree is not empty sum+= distance
between current and last event point.
Complexity of sum of intervals O(n log n)
Complexity of area of union of rectangles O(n2 log n)
Can we do better??
Plane Sweep Algorithm 18/27
Sum of the union of the intervals
δx
Naïve Method:
At each event point find out y by a sweepline method.
event points: Left and right end point of an interval.
status: Balanced binary search tree to store intervals.
At each event point if tree is not empty sum+= distance
between current and last event point.
Complexity of sum of intervals O(n log n)
Complexity of area of union of rectangles O(n2 log n)
Can we do better??How to maintain sum of the union of the
intervals with respect to insertion and deletion
Plane Sweep Algorithm 18/27
Sum of the union of the intervals
Sort the end points of the intervals.
This will create a set of elementary intervals.
Plane Sweep Algorithm 19/27
Sum of the union of the intervals
Sort the end points of the intervals.
This will create a set of elementary intervals.
Plane Sweep Algorithm 19/27
Sum of the union of the intervals
Sort the end points of the intervals.
This will create a set of elementary intervals.
Depending on which intervals are active , a set of
elementary intervals will be active .
Plane Sweep Algorithm 19/27
Interval-Tree
We maintain a special data structure called the
interval-tree
Plane Sweep Algorithm 20/27
Interval-Tree
We maintain a special data structure called the
interval-tree
It is a balanced binary tree T of the elementory
intervals.
Plane Sweep Algorithm 20/27
Interval-Tree
We maintain a special data structure called the
interval-tree
It is a balanced binary tree T of the elementory
intervals.
Each node represents an interval.
Plane Sweep Algorithm 20/27
Interval-Tree
How an interval I is stored in the tree?
Plane Sweep Algorithm 21/27
Interval-Tree
How an interval I is stored in the tree?
Start with the root and proceed.
Plane Sweep Algorithm 21/27
Interval-Tree
How an interval I is stored in the tree?
Start with the root and proceed.
Plane Sweep Algorithm 21/27
Interval-Tree
Algorithm 3 ReportInterval(T , v , I )
1: if v ⊆ I then
2: Report v
3: return
4: end if
5: if I ∩ lc(v ) 6= emptyset then
6: ReportInterval(T , lc(v ), I ∩ lc(v ))
7: end if
8: if I ∩ rc(v ) 6= emptyset then
9: ReportInterval(T , rc(v ), I ∩ rc(v ))
10: end if
Plane Sweep Algorithm 22/27
Interval-Tree
Claim: Each interval is stored in O(log n) nodes.
Plane Sweep Algorithm 23/27
Interval-Tree
Claim: Each interval is stored in O(log n) nodes.
At each level there can be at most two nodes representing the
interval.
All of them have to be consecutive.
Plane Sweep Algorithm 23/27
Interval-Tree
Claim: Each interval is stored in O(log n) nodes.
At each level there can be at most two nodes representing the
interval.
All of them have to be consecutive.
Plane Sweep Algorithm 23/27
Interval-Tree
Each interval can be inserted and deleted in O(log n) time.
At each node we maintain the length of the active elementary
intervals.
Plane Sweep Algorithm 24/27
Interval-Tree
7
7
4 3
3 1 3
Each interval can be inserted and deleted in O(log n) time.
At each node we maintain the length of the active elementary
intervals.
Plane Sweep Algorithm 24/27
Interval-Tree
7
7
4 3
3 1 3
Each interval can be inserted and deleted in O(log n) time.
At each node we maintain the length of the active elementary
intervals.
Plane Sweep Algorithm 24/27
Interval-Tree
7
7
4 6
3 1 3 3
Each interval can be inserted and deleted in O(log n) time.
At each node we maintain the length of the active elementary
intervals.
Plane Sweep Algorithm 24/27
Interval-Tree
7
7
10
4 6
3 1 3 3
Each interval can be inserted and deleted in O(log n) time.
At each node we maintain the length of the active elementary
intervals.
Plane Sweep Algorithm 24/27
Interval-Tree
10
10
10
4 6
3 1 3 3
Each interval can be inserted and deleted in O(log n) time.
At each node we maintain the length of the active elementary
intervals.
Plane Sweep Algorithm 24/27
Interval-Tree
10
10
10
4 6
3 1 3 3
O(log n) insert each takes O(log n) time.
In time O(log2 n) we can perform the updates.
Plane Sweep Algorithm 25/27
Interval-Tree
10
10
10
4 6
3 1 3 3
O(log n) insert each takes O(log n) time.
In time O(log2 n) we can perform the updates.
Can be done in time O(log n)
Plane Sweep Algorithm 25/27
Interval-Tree
Can be done in time O(log n).
Plane Sweep Algorithm 26/27
Interval-Tree
Can be done in time O(log n).
Consider the left most and right most elementary intervals.
Plane Sweep Algorithm 26/27
Interval-Tree
Can be done in time O(log n).
Consider the left most and right most elementary intervals.
Plane Sweep Algorithm 26/27
Interval-Tree
Can be done in time O(log n).
Consider the left most and right most elementary intervals.
Plane Sweep Algorithm 26/27
Sum of the union of the intervals
In time O(n log n) we can find out the area of the union of n
rectangles.
Plane Sweep Algorithm 27/27
