Line Sweep
Line sweep algorithms process a set of points or segments by sweeping a conceptual line across the plane, stopping to handle events as the sweep line hits endpoints. This reduces problems to 1D.
Java example for rectangle intersection:


C++ example for interval intersection:


Python example for closest pair:


Line sweep reduces problems to 1D while handling events, often speeding up computational geometry algorithms.
Line sweep is an algorithmic technique where a virtual line moves across the plane to solve geometric problems, such as finding intersections, calculating union length, and more. Let’s explore a simple example to understand the concept: finding all intersecting pairs of a given set of line segments on a plane.
Problem
You have a set of horizontal line segments, and you want to find all the pairs that intersect at their endpoints.
Line Sweep Solution
 Sort the Endpoints: First, you need to sort the endpoints of the line segments based on their xcoordinates.
 Sweep Line: Imagine a vertical line (called the sweep line) that moves from left to right across the plane.
 Handle Events: As the sweep line encounters the endpoints of the segments, it performs specific actions:
 When the sweep line reaches the left endpoint of a segment, add that segment to a set (e.g., a balanced binary tree).
 When the sweep line reaches the right endpoint of a segment, remove that segment from the set and check if its neighbors in the set intersect with it.
 Record Intersections: If two neighboring segments intersect, record this intersection.
Pseudocode
sort(endpoints)
for endpoint in endpoints:
if endpoint is left:
add segment to set
else:
check intersection with neighbors in set
remove segment from set
Visual Explanation
Segments: ___________ ________ ____________
Sweep Line:     
Events: Left Right Left Right Left Right
Key Takeaway
 The line sweep algorithm efficiently handles geometric problems by sorting events and processing them as a virtual line sweeps across the plane.
 In this simple example, line sweep is used to find intersecting pairs of horizontal line segments, making the problem more tractable by breaking it down into a sequence of simple events.