Coordinate compression and sweep line

A common geometry problem gives you many rectangles on a 2D plane and asks how much total area they cover. The coordinates can run as high as $10^9$, so a 2D array indexed directly by coordinate is out of the question. Coordinate compressioncoordinate compressionMapping large coordinate values to small ranks to enable dense array storage for sparse 2D problems.In the glossary maps those large coordinates down to a small, dense range, and a 2D difference array does the counting on that dense grid instead.

Coordinate compression

Compression replaces each distinct coordinate with its rank in sorted order. Take the x-coordinates [1, 5, 10, 3]. Sort them to [1, 3, 5, 10], then map 1 -> 0, 3 -> 1, 5 -> 2, 10 -> 3. Every value now fits inside an array indexed 0 to 3, no matter how far apart the original values were.

To compress a list, collect the distinct coordinates, sort them, and build a dictionary from each value to its position in that sorted list.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    n = int(input_data[0])7    coords = list(map(int, input_data[1:n + 1]))8
9    sorted_coords = sorted(set(coords))10    rank_map = {v: i for i, v in enumerate(sorted_coords)}11
12    compressed = [rank_map[c] for c in coords]13    print(" ".join(map(str, compressed)))14
15
16if __name__ == "__main__":17    main()

4
1 5 10 3

0 2 3 1

Compression only helps when you also remember the real gap between consecutive ranks. Take two rectangles: one from x=0 to 10 and y=0 to 10, the other from x=5 to 15 and y=5 to 15. The distinct x-coordinates are [0, 5, 10, 15], and so are the y-coordinates. The first rectangle spans x-ranks 0 to 2 and y-ranks 0 to 2; the second spans x-ranks 1 to 3 and y-ranks 1 to 3. A 4x4 compressed grid now stands in for a 15x15 region, and the real width of the cell between rank i and rank i + 1 is sorted_x[i + 1] - sorted_x[i].

A 2D difference array on the compressed grid

A 2D difference array extends the 1D idea from earlier stages. To add a rectangle to it, increment the top-left corner, decrement the two corners that share an edge with it, and increment the bottom-right corner. Once every rectangle is added, a 2D prefix sum recovers, for each compressed cell, how many rectangles cover it.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    n = int(input_data[0])7
8    xs = []9    ys = []10    rects = []11
12    for i in range(n):13        x1 = int(input_data[1 + i * 4])14        y1 = int(input_data[1 + i * 4 + 1])15        x2 = int(input_data[1 + i * 4 + 2])16        y2 = int(input_data[1 + i * 4 + 3])17        rects.append((x1, y1, x2, y2))18        xs.extend([x1, x2])19        ys.extend([y1, y2])20
21    xs = sorted(set(xs))22    ys = sorted(set(ys))23
24    # Create difference array25    diff = [[0] * len(ys) for _ in range(len(xs))]26
27    # Add rectangles to difference array28    for x1, y1, x2, y2 in rects:29        xi1 = xs.index(x1)30        yi1 = ys.index(y1)31        xi2 = xs.index(x2)32        yi2 = ys.index(y2)33
34        diff[xi1][yi1] += 135        diff[xi2][yi1] -= 136        diff[xi1][yi2] -= 137        diff[xi2][yi2] += 138
39    # Compute 2D prefix sum40    area = 041    for i in range(len(xs) - 1):42        for j in range(len(ys) - 1):43            if i > 0:44                diff[i][j] += diff[i - 1][j]45            if j > 0:46                diff[i][j] += diff[i][j - 1]47            if i > 0 and j > 0:48                diff[i][j] -= diff[i - 1][j - 1]49
50            if diff[i][j] > 0:51                width = xs[i + 1] - xs[i]52                height = ys[j + 1] - ys[j]53                area += width * height54
55    print(area)56
57
58if __name__ == "__main__":59    main()

2
0 0 10 10
5 5 15 15

175

Here the two rectangles from the example above overlap in the region from x=5 to 10 and y=5 to 10. Each covers 100 square units on its own, their overlap is 25, so the total area covered by at least one of them is 100 + 100 - 25 = 175, which is what the program prints. The prefix sum step turns the four corner updates into a covering count per cell, and multiplying each covered cell by its real width and height, then summing, converts that count into a real area instead of a cell count.

Sweeping across sorted events

A sweep line is an imaginary line that moves across the plane in sorted order, updating a running total each time it crosses an event. On a 1D line, the events are interval starts and ends.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    n = int(input_data[0])7
8    events = []9    for i in range(n):10        start = int(input_data[1 + i * 2])11        end = int(input_data[1 + i * 2 + 1])12        events.append((start, 1))13        events.append((end, -1))14
15    events.sort()16
17    total_coverage = 018    active_count = 019    prev_pos = events[0][0]20
21    for pos, delta in events:22        if active_count > 0 and pos > prev_pos:23            # This stretch is covered by at least one interval, so it counts24            # once no matter how many intervals overlap it here.25            total_coverage += pos - prev_pos26
27        active_count += delta28        prev_pos = pos29
30    print(total_coverage)31
32
33if __name__ == "__main__":34    main()

3
0 5
3 8
6 10

10

Sort every start and end by position, then walk through them left to right, keeping a count of how many intervals are currently active. Between two consecutive events, the count does not change, so that stretch is either fully covered or fully uncovered. With intervals [0, 5], [3, 8], and [6, 10], the covered stretches are [0, 5], [3, 8], and [6, 10], which together cover every point from 0 to 10 without a gap. The total union length is 10.

Notice that the running total only adds a stretch's length once, regardless of how many intervals are active there. Multiplying the stretch length by the active count would answer a different question, the sum of each interval's own length, which needs no sweep at all. The active count exists to tell you whether a stretch is covered, not to weight it.

Why compression works and where it stops helping

Compression works because only the relative order of coordinates matters for computing areas and overlaps, not their absolute values. A thousand rectangles contribute at most 2,000 distinct x-coordinates, one endpoint each on the left and right. Mapping those to ranks 0 through 1,999 needs a 2,000 by 2,000 array, about 4 million cells, instead of an array sized $10^9$ by $10^9$, which no computer could hold.

The same compression assumes a dense grid built from every distinct coordinate is worth building. If a problem only ever asks about the coordinates that actually appear, the dense grid does the job. If it asks about many additional query points that were never among the original coordinates, you need to insert those points into the sorted coordinate list too, or the compressed ranks will not line up with the real question being asked.

Common mistakes

The most common mistake is forgetting to weight by real dimensions. The 2D prefix sum over a compressed grid gives you a covering count per cell, not an area. Before summing, multiply each covered cell by sorted_x[i + 1] - sorted_x[i] and sorted_y[j + 1] - sorted_y[j]. Skip that step and you get the number of cell intersections, a number with no direct meaning in the original coordinates.

A second mistake is getting the four corners of a rectangle update wrong. Adding a rectangle needs an increment at its top-left corner, a decrement at each of the two corners that share exactly one of its edges, and an increment at its bottom-right corner. Missing one of these four, or using the wrong rank for one of them, corrupts every prefix sum computed afterward.

A third mistake is confusing a rank with the coordinate it stands for. After sorting [1, 5, 10, 3] to [1, 3, 5, 10], rank 1 stands for the value 3, not the value 1. A rectangle from x=3 to x=5 uses ranks 1 to 2, not the literal numbers 3 and 5. Keep the value-to-rank dictionary next to the compressed array and always go through it, rather than trying to do rank arithmetic from memory.

Recap

Coordinate compression turns coordinates that span up to a billion into small, dense ranks, so a 2D difference array can answer aggregate questions about them. Weighting each compressed cell by its real width and height converts a covering count back into a real area. A sweep line answers a different kind of question, walking sorted events left to right and updating a running total exactly when the state changes, which is how you get a union length instead of a sum of individual pieces.