Closest Pair
The closest pair problem is a classic geometric problem where we are given a set of points in a 2D plane, and the goal is to find the pair of points with the smallest Euclidean distance between them. The sweep line algorithm provides an efficient solution to this problem.
Let’s see how the sweep line algorithm can be used to find the closest pair of points:
1. Sort the points based on their x-coordinates.
2. Initialize a variable `min_dist` to store the minimum distance and a pair `closest_pair` to store the closest pair of points.
3. Initialize an empty BST to store the points currently intersecting the sweep line.
4. Process the points in the sorted order:
- Insert the current point into the BST.
- Find the points in the BST that are within a vertical distance of `min_dist` from the current point.
- For each point found, calculate the Euclidean distance between it and the current point.
- If a smaller distance is found, update `min_dist` and `closest_pair`.
- Remove from the BST any points that are no longer within a horizontal distance of `min_dist` from the current point.
5. Return the `closest_pair` of points.
The sweep line algorithm efficiently solves the closest pair problem by reducing the number of distance calculations needed. It maintains a BST of points within a vertical strip of width `min_dist` and only considers points within that strip for distance calculations.
For example :
import math
def distance(p1, p2):
return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
def closest_pair(points):
points.sort(key=lambda x: x[0]) # Sort based on x-coordinates
min_dist = float('inf')
closest_pair = None
bst = []
def insert(point):
bst.append(point)
bst.sort(key=lambda x: x[1]) # Sort based on y-coordinates
def remove(point):
bst.remove(point)
def find_points_in_range(point, dist):
idx = bisect.bisect_left(bst, (point[0], point[1] - dist))
while idx < len(bst) and bst[idx][1] <= point[1] + dist:
yield bst[idx]
idx += 1
for point in points:
insert(point)
for p in find_points_in_range(point, min_dist):
d = distance(point, p)
if d < min_dist:
min_dist = d
closest_pair = (point, p)
remove(point)
return closest_pair
In this code, the `distance` function calculates the Euclidean distance between two points. The `closest_pair` function performs the sweep line algorithm. It sorts the points based on x-coordinates, initializes the `min_dist` and `closest_pair` variables, and maintains a BST of points sorted by y-coordinates.
The algorithm processes each point in the sorted order, inserts it into the BST, finds the points within a vertical distance of `min_dist` using the `find_points_in_range` function, and updates `min_dist` and `closest_pair` if a closer pair is found. Finally, it removes the current point from the BST.
The time complexity of the sweep line algorithm for the closest pair problem is O(n log n), where n is the number of points. This is because sorting the points takes O(n log n) time, and processing each point takes O(log n) time for BST operations and O(log n) time for finding points within the vertical strip.
Line Segment Intersections
Another important application of the sweep line algorithm is detecting line segment intersections. Given a set of line segments in a 2D plane, the goal is to find all the intersection points between the line segments efficiently.
The sweep line algorithm can be used to solve the line segment intersection problem by following below mentioned steps:
1. Sort the endpoints of the line segments based on their x-coordinates.
2. Initialize an empty BST to store the line segments currently intersecting the sweep line.
3. Process the endpoints in the sorted order:
- If the endpoint is the left endpoint of a line segment, insert the line segment into the BST.
- If the endpoint is the right endpoint of a line segment, remove the line segment from the BST.
- If the endpoint is an intersection point, report it.
4. For each line segment being inserted into the BST, check for intersections with the line segments already in the BST.
The key idea is to maintain a BST of line segments sorted by their y-coordinates at the current x-coordinate of the sweep line. As the sweep line moves from left to right, line segments are inserted and removed from the BST based on their endpoints. Whenever a new line segment is inserted, we check for intersections with the line segments already in the BST.
For example :
class LineSegment:
def __init__(self, start, end):
self.start = start
self.end = end
def intersects(self, other):
# Check if two line segments intersect
# Return the intersection point if they intersect, None otherwise
# You can use any line segment intersection algorithm here
def find_intersections(segments):
events = []
for segment in segments:
events.append((segment.start, 'start', segment))
events.append((segment.end, 'end', segment))
events.sort()
bst = []
intersections = []
def insert(segment):
# Insert the line segment into the BST
# Check for intersections with the line segments already in the BST
# Report any intersection points found
pass
def remove(segment):
# Remove the line segment from the BST
pass
for event in events:
point, event_type, segment = event
if event_type == 'start':
insert(segment)
else:
remove(segment)
return intersections
In this code, the `LineSegment` class represents a line segment with start and end points. The `intersects` method checks if two line segments intersect and returns the intersection point if they do. You can use any line segment intersection algorithm within this method.
The `find_intersections` function performs the sweep line algorithm. It creates an event list by collecting the start and end points of all the line segments and sorting them based on their x-coordinates. It initializes an empty BST and a list to store the intersection points.
The algorithm processes each event in the sorted order. If the event is a start point, the corresponding line segment is inserted into the BST, and intersections with the line segments already in the BST are checked. If the event is an end point, the corresponding line segment is removed from the BST.
The `insert` and `remove` functions handle the insertion and removal of line segments from the BST, respectively. Inside the `insert` function, you need to implement the logic to check for intersections with the line segments already in the BST and report any intersection points found.
The time complexity of the sweep line algorithm for line segment intersection is O((n + k) log n), where n is the number of line segments and k is the number of intersection points. The sorting of events takes O(n log n) time, and processing each event takes O(log n) time for BST operations. The total time complexity depends on the number of intersections found.
Union Of Rectangles
The sweep line algorithm can also be used to calculate the union of rectangles. Given a set of rectangles in a 2D plane, the goal is to find the total area covered by the union of all the rectangles.
The sweep line algorithm solves this problem by maintaining a balanced binary search tree (BST) that stores the active intervals (y-coordinates) of the rectangles intersecting the sweep line. As the sweep line moves from left to right, the BST is updated to reflect the changes in the active intervals.
Let’s see how the sweep line algorithm can be used to calculate the union of rectangles:
1. Sort the x-coordinates of all the rectangle edges (left and right edges).
2. Initialize an empty BST to store the active intervals and a variable `total_area` to store the total area.
3. Process the x-coordinates in the sorted order:
- If the current x-coordinate is the left edge of a rectangle, insert the y-interval of the rectangle into the BST.
- If the current x-coordinate is the right edge of a rectangle, remove the y-interval of the rectangle from the BST.
- Calculate the length of the interval between the current x-coordinate and the next x-coordinate.
- Multiply the interval length by the total height of the active intervals in the BST and add it to `total_area`.
4. Return the `total_area`.
The BST used in this algorithm should support efficient interval operations, such as insertion, deletion, and querying the total height of active intervals. A common choice is to use a self-balancing BST like a Red-Black tree or an AVL tree.
For example :
class Rectangle:
def __init__(self, x1, y1, x2, y2):
self.x1 = x1
self.y1 = y1
self.x2 = x2
self.y2 = y2
def union_of_rectangles(rectangles):
events = []
for rect in rectangles:
events.append((rect.x1, 'start', rect))
events.append((rect.x2, 'end', rect))
events.sort()
bst = []
total_area = 0
prev_x = events[0][0]
def get_total_height():
# Calculate the total height of active intervals in the BST
# You can use an interval tree or a segment tree for efficient querying
pass
for event in events:
x, event_type, rect = event
if event_type == 'start':
bst.append((rect.y1, rect.y2))
else:
bst.remove((rect.y1, rect.y2))
interval_length = x - prev_x
total_height = get_total_height()
total_area += interval_length * total_height
prev_x = x
return total_area
In this code, the `Rectangle` class represents a rectangle with its coordinates. The `union_of_rectangles` function performs the sweep line algorithm. It creates an event list by collecting the left and right edges of all the rectangles and sorting them based on their x-coordinates.
The algorithm processes each event in the sorted order. If the event is a start event (left edge), the corresponding y-interval is inserted into the BST. If the event is an end event (right edge), the corresponding y-interval is removed from the BST.
At each event, the length of the interval between the current x-coordinate and the next x-coordinate is calculated. The total height of the active intervals in the BST is computed using the `get_total_height` function, which can be implemented using an interval tree or a segment tree for efficient querying.
The total area is updated by multiplying the interval length by the total height of active intervals and adding it to `total_area`.
The time complexity of the sweep line algorithm for the union of rectangles problem is O(n log n), where n is the total number of rectangle edges. The sorting of events takes O(n log n) time, and processing each event takes O(log n) time for BST operations.
Convex Hull
The convex hull of a set of points is the smallest convex polygon that contains all the points. The sweep line algorithm can be used to construct the convex hull efficiently.
Let’s see how sweep line algorithm for constructing the convex hull works :
1. Sort the points based on their x-coordinates. If two points have the same x-coordinate, sort them based on their y-coordinates.
2. Initialize two empty lists, `upper_hull` and `lower_hull`, to store the points on the upper and lower parts of the convex hull, respectively.
3. Process the points in the sorted order:
- For each point, while there are at least two points in `upper_hull` and the last two points in `upper_hull` along with the current point form a clockwise turn, remove the last point from `upper_hull`.
- Append the current point to `upper_hull`.
4. Process the points in the reverse sorted order:
- For each point, while there are at least two points in `lower_hull` and the last two points in `lower_hull` along with the current point form a clockwise turn, remove the last point from `lower_hull`.
- Append the current point to `lower_hull`.
5. Concatenate `upper_hull` and `lower_hull` (excluding the duplicate first and last points) to obtain the complete convex hull.
The key idea behind the sweep line algorithm for convex hull is to maintain the upper and lower parts of the hull separately. The upper hull is constructed by processing the points from left to right, while the lower hull is constructed by processing the points from right to left.
For example :
def orientation(p, q, r):
return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
def convex_hull(points):
points.sort()
upper_hull = []
lower_hull = []
for point in points:
while len(upper_hull) >= 2 and orientation(upper_hull[-2], upper_hull[-1], point) <= 0:
upper_hull.pop()
upper_hull.append(point)
for point in reversed(points):
while len(lower_hull) >= 2 and orientation(lower_hull[-2], lower_hull[-1], point) <= 0:
lower_hull.pop()
lower_hull.append(point)
convex_hull = upper_hull[:-1] + lower_hull[:-1]
return convex_hull
In this code, the `orientation` function determines the orientation of three points. It returns a positive value if the points form a counterclockwise turn, a negative value if they form a clockwise turn, and zero if they are collinear.
The `convex_hull` function performs the sweep line algorithm. It first sorts the points based on their x-coordinates (and y-coordinates in case of ties). Then, it processes the points from left to right to construct the upper hull. For each point, it checks if the last two points in `upper_hull` along with the current point form a clockwise turn. If so, it removes the last point from `upper_hull` until a counterclockwise turn is formed. Finally, it appends the current point to `upper_hull`.
Similarly, it processes the points from right to left to construct the lower hull, following the same logic.
The final convex hull is obtained by concatenating `upper_hull` and `lower_hull`, excluding the duplicate first and last points.
The time complexity of the sweep line algorithm for constructing the convex hull is O(n log n), where n is the number of points. The sorting step takes O(n log n) time, and processing each point takes O(n) time in the worst case, resulting in a total time complexity of O(n log n).
Manhattan Minimum Spanning Tree (MST)
The Manhattan minimum spanning tree (MST) is a variant of the minimum spanning tree problem specific to the Manhattan distance metric. In this problem, we are given a set of points in a 2D plane, and the goal is to find the minimum spanning tree that connects all the points using only horizontal and vertical edges.
The sweep line algorithm can be used to construct the Manhattan MST efficiently by following below mentioned steps : .
1. Sort the points based on their x-coordinates.
2. Initialize an empty set, `mst_edges`, to store the edges of the Manhattan MST.
3. Process the points in the sorted order:
- For each point, find the nearest point above and below it that has already been processed.
- Add the horizontal edge connecting the current point to the nearest point above (if exists) to `mst_edges`.
- Add the horizontal edge connecting the current point to the nearest point below (if exists) to `mst_edges`.
- Add the vertical edge connecting the current point to its predecessor in the sorted order (if exists) to `mst_edges`.
4. Return the `mst_edges` as the Manhattan MST.
The sweep line algorithm for Manhattan MST maintains a balanced binary search tree (BST) to store the processed points sorted by their y-coordinates. For each point, it finds the nearest points above and below it in the BST and adds the corresponding horizontal edges to the MST. Additionally, it adds the vertical edge connecting the current point to its predecessor in the sorted order.
For example :
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def manhattan_distance(p1, p2):
return abs(p1.x - p2.x) + abs(p1.y - p2.y)
def manhattan_mst(points):
points.sort(key=lambda p: p.x)
bst = []
mst_edges = []
def find_nearest_above(point):
# Find the nearest point above the given point in the BST
# Return the point if found, None otherwise
pass
def find_nearest_below(point):
# Find the nearest point below the given point in the BST
# Return the point if found, None otherwise
pass
def add_point(point):
# Add the point to the BST
pass
for i in range(len(points)):
point = points[i]
above = find_nearest_above(point)
below = find_nearest_below(point)
if above:
mst_edges.append((point, above))
if below:
mst_edges.append((point, below))
if i > 0:
mst_edges.append((point, points[i-1]))
add_point(point)
return mst_edges
In this code, the `Point` class represents a point with x and y coordinates. The `manhattan_distance` function calculates the Manhattan distance between two points.
The `manhattan_mst` function performs the sweep line algorithm. It first sorts the points based on their x-coordinates. Then, it initializes an empty BST and a list to store the edges of the Manhattan MST.
For each point, it finds the nearest point above and below it in the BST using the `find_nearest_above` and `find_nearest_below` functions, respectively. These functions can be implemented using the BST operations to find the nearest points efficiently.
If a nearest point above or below exists, the corresponding horizontal edge is added to `mst_edges`. Additionally, the vertical edge connecting the current point to its predecessor in the sorted order is added to `mst_edges`.
Finally, the current point is added to the BST using the `add_point` function.
The time complexity of the sweep line algorithm for constructing the Manhattan MST is O(n log n), where n is the number of points. The sorting step takes O(n log n) time, and processing each point takes O(log n) time for BST operations, resulting in a total time complexity of O(n log n).
Frequently Asked Questions
What is the main idea behind the sweep line algorithm?
The sweep line algorithm processes geometric objects in a specific order by maintaining a balanced binary search tree (BST) of active objects and updating the solution as the sweep line progresses.
What is the time complexity of the sweep line algorithm for the closest pair problem?
The time complexity of the sweep line algorithm for the closest pair problem is O(n log n), where n is the number of points.
How does the sweep line algorithm handle line segment intersections?
The sweep line algorithm maintains a BST of line segments sorted by their y-coordinates at the current x-coordinate of the sweep line. It checks for intersections whenever a new line segment is inserted into the BST.
Conclusion
In this article, we talked about the sweep line algorithm and its applications which helps in solving different geometric problems. We learned how the sweep line technique efficiently processes geometric objects by maintaining a balanced binary search tree and updating the solution as the sweep line progresses. We also discussed specific applications such as finding the closest pair of points, detecting line segment intersections, calculating the union of rectangles, constructing the convex hull, and building the Manhattan minimum spanning tree.
You can also check out our other blogs on Code360.
139+ registered 
