The Line Sweep Technique on Points

The Line Sweep Technique on Points

Imagine a line of dominoes standing on a long ruler. You walk past them from the left end to the right end, and as you pass each one you do something — knock it over, count it, or note it down. That simple idea — moving across a set of things in order and keeping track of what you have seen so far — is the heart of the line sweep technique.

In computer science, the "ruler" is the x-axis of a graph (the Cartesian plane), and the "dominoes" are events marked at certain positions on that axis. The line sweep technique is a clean and efficient way to solve problems where these events sit on an axis.

What is an "event point"?

An event is just a single position on the axis that means something to the problem. Often these events come from intervals.

An interval is a stretch with a beginning and an end — for example, the interval 2 , 5 covers everything from 2 up to 5. On the axis, that interval is described by two single points: a start point at 2 and an end point at 5.

start          end
  2 ───────────── 5

So instead of thinking about the whole stretch at once, we break it into two simple events: "something begins here" and "something ends here." Events don't always have to come from intervals — they can be plain points too — but turning intervals into points is the most common use.

Step 1: Convert intervals to points

Suppose we are given this array of intervals:

array of intervals (index):  0      1      2      3
                            2,5    4,9    5,7    1,4

We take each interval and split it into two separate points — a start point and an end point — and put them all into one new array. Each point is clearly labelled so we never forget which kind it is:

array of points (index): 0        1      2       3
                        2 start  5 end  4 start  9 end

                         4        5      6       7
                        5 start  7 end  1 start  4 end

Notice the new array is twice as long. If the original had N intervals, the points array has 2 * N entries.

Step 2: Sort the points

The line sweep idea only works if we visit the events in order along the axis, from left to right. So we sort the points by their value, in non-decreasing order (smallest first, equal values allowed to sit next to each other).

After sorting, the array looks like this:

sorted array of points (index): 0        1        2      3
                                1 start  2 start  4 end  4 start

                                 4       5        6      7
                                5 end    5 start  7 end  9 end

Once the array is sorted, reading it from index 0 to the last index is exactly the same as walking along the x-axis from left to right. The array *becomes* a picture of the axis.

Tie-breaking rule: what if a start point and an end point have the same value? For example, both a 4 end and a 4 start exist above. The common rule is to put the end point before the start point. The reason: when one interval ends and another begins at the very same spot, we usually want to "close" the old one before "opening" the new one. But this rule can change depending on what a particular problem needs.

Step 3: Sweep the line

Now we do the sweep. Picture a vertical line standing at the far left of the axis, then sliding to the right. Every time it touches one of our sorted points, we process that point.

In code, this "sliding line" is nothing magical — it is simply a loop that walks through the sorted array one element at a time:

for each point in sorted array (left to right):
    process the point
    update the state

As we move, we keep a small piece of memory called the state. The state is some data structure that remembers what is happening right now. Common choices are:

• an event counter (for example, "how many intervals are currently open?"),
• a set (which items are active right now),
• a list (a running collection of results).

Each time the sweep line hits a start point, we might increase the counter (one more interval has opened). Each time it hits an end point, we might decrease it (one interval has closed). By watching how the state changes, we can detect overlaps, merge intervals, find the busiest moment, and solve many other problems — all in a single pass.

When the loop reaches the end of the array, the sweep is complete. Iterating through the sorted array is the same as sweeping a line through every point and processing them in order.

Why this works so well

The power of line sweep is that you never have to compare every interval with every other interval. You sort once, then make one tidy left-to-right pass, updating a small state as you go. Hard-looking geometry problems turn into simple bookkeeping.

Complexity Analysis

Let N be the number of items.

• Splitting intervals into points and sorting them takes O(N log N) time (sorting dominates).
• The sweep itself visits each point exactly once, which is linear O(N) time.
• Added together, the time is O(N log N) in every case.

For space, it depends on the input:

• Best case — given an array of points already: we may be able to sort the input in place without any extra array. Space is O(1), time is O(N log N).
• Worst case — given an array of intervals: we must build a new points array of size 2 * N, so space is O(N), time is O(N log N).