22.05Intermediate4 topics21 min4 interactive animations

Two-dimensional sweep line

Sweeping a line across the plane: the skyline of rectangles, orthogonal segment intersections, the closest pair of points and the ordered sets these sweeps rely on.

Learning goals

Compute a skyline with a sweep and a multiset of active heights
Count crossings between horizontal and vertical segments
Find the closest pair of points in O(n log n) with a sorted active window
Use TreeMap and TreeSet operations as the ordered event set of a sweep

Prerequisites

One-dimensional sweep lineTreeMap and TreeSet

Two-dimensional geometry looks hard, but a vertical sweep line reduces it to a one-dimensional problem about the objects that currently cross the line.

22.05.1

Rectangle union outline

The **skyline** problem gives buildings as (left, right, height) and asks for the outline of their union as a list of key points where the height changes. Sweep left to right over events: a building's left edge adds its height to the active multiset, its right edge removes it. After processing all events at one x, the current height is the largest value in the multiset; if it differs from the last reported height, output a key point.

In the “Classic” preset the outline is (2,10), (3,15), (7,12), (12,0), (15,10), (20,8), (24,0): the tall building at x = 3 hides the first, and when it ends at 7 the third takes over at height 12. “Same height touching” (0-2 at height 3 and 2-5 at height 3) produces no key point at x = 2, because the height does not change, and “One hides another” shows a smaller building inside a larger one adding nothing.

Java

1// buildings[i] = {left, right, height}; returns key points {x, height}
2static List<int[]> skyline(int[][] buildings) {
3    List<int[]> events = new ArrayList<>();                  // {x, height}: height > 0 is a start, < 0 is an end
4    for (int[] b : buildings) {
5        events.add(new int[]{b[0], b[2]});
6        events.add(new int[]{b[1], -b[2]});
7    }
8    events.sort((p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(q[1], p[1]));  // starts first, tallest first
9    TreeMap<Integer, Integer> active = new TreeMap<>();      // height -> how many active buildings have it
10    active.put(0, 1);
11    List<int[]> result = new ArrayList<>();
12    int last = 0;
13    for (int[] e : events) {
14        if (e[1] > 0) active.merge(e[1], 1, Integer::sum);
15        else if (active.merge(-e[1], -1, Integer::sum) == 0) active.remove(-e[1]);
16        int top = active.lastKey();
17        if (top != last) { result.add(new int[]{e[0], top}); last = top; }
18    }
19    return result;
20}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

Skyline: sweep with a multiset of heights

Interactive · edit the input

B1 h=10

[2, 9]

B2 h=15

[3, 7]

B3 h=12

[5, 12]

B4 h=10

[15, 20]

B5 h=8

[19, 24]

0123456789101112131415161718192021222324

events (x, ±height)

2:-10

3:-15

5:-12

7:15

9:10

12:12

15:-10

19:-8

20:10

24:8

active heights (max last)

outline key points

none

Setup

Each building gives a start event (negative height) and an end event. Sweep left to right, keeping every active height. Whenever the tallest active height changes, the outline has a key point.

Step 1 / 12

Java

1static List<int[]> skyline(int[][] b) {                         // b[i] = {left, right, height}
2    List<int[]> ev = new ArrayList<>();
3    for (int[] x : b) { ev.add(new int[]{x[0], -x[2]}); ev.add(new int[]{x[1], x[2]}); }   // start: negative height
4    ev.sort((p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(p[1], q[1]));
5    TreeMap<Integer, Integer> active = new TreeMap<>(); active.put(0, 1);               // height -> count; the ground
6    List<int[]> out = new ArrayList<>(); int prev = 0;
7    for (int[] e : ev) {
8        int h = Math.abs(e[1]);
9        if (e[1] < 0) active.merge(h, 1, Integer::sum);                                  // a building starts
10        else if (active.merge(h, -1, Integer::sum) == 0) active.remove(h);               // a building ends
11        int top = active.lastKey();                                                      // the tallest active building
12        if (top != prev) { out.add(new int[]{e[0], top}); prev = top; }                  // the outline changes here
13    }
14    return out;
15}

Live state

buildings

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L2	buildings=5	Each building gives a start event (negative height) and an end event. Sweep left to right, keeping every active height. Whenever the tallest active height changes, the outline has a key point.
2	L12	x=2 event=start h=10 top=10 outline=1	At x = 2 a building of height 10 starts. The tallest active height is 10: it changed, so (2, 10) is a key point.
3	L12	x=3 event=start h=15 top=15 outline=2	At x = 3 a building of height 15 starts. The tallest active height is 15: it changed, so (3, 15) is a key point.
4	L12	x=5 event=start h=12 top=15 outline=2	At x = 5 a building of height 12 starts. The tallest active height is 15: unchanged, so the outline continues.
5	L12	x=7 event=end h=15 top=12 outline=3	At x = 7 a building of height 15 ends. The tallest active height is 12: it changed, so (7, 12) is a key point.
6	L12	x=9 event=end h=10 top=12 outline=3	At x = 9 a building of height 10 ends. The tallest active height is 12: unchanged, so the outline continues.
7	L12	x=12 event=end h=12 top=0 outline=4	At x = 12 a building of height 12 ends. The tallest active height is 0: it changed, so (12, 0) is a key point.
8	L12	x=15 event=start h=10 top=10 outline=5	At x = 15 a building of height 10 starts. The tallest active height is 10: it changed, so (15, 10) is a key point.
9	L12	x=19 event=start h=8 top=10 outline=5	At x = 19 a building of height 8 starts. The tallest active height is 10: unchanged, so the outline continues.
10	L12	x=20 event=end h=10 top=8 outline=6	At x = 20 a building of height 10 ends. The tallest active height is 8: it changed, so (20, 8) is a key point.
11	L12	x=24 event=end h=8 top=0 outline=7	At x = 24 a building of height 8 ends. The tallest active height is 0: it changed, so (24, 0) is a key point.
12	L14	return=[(2, 10), (3, 15), (7, 12), (12, 0), (15, 10), (20, 8), (24, 0)]	Skyline key points: [(2, 10), (3, 15), (7, 12), (12, 0), (15, 10), (20, 8), (24, 0)]. O(n log n): the sort plus O(log n) per event on the ordered multiset.

22.05.2

Orthogonal intersections

Count the places where horizontal segments (y, x1-x2) cross vertical segments (x, y1-y2). Sweep along x. When the sweep reaches a horizontal segment's left end, insert its y into an ordered set; at its right end remove it. At a vertical segment, every active y within [y1, y2] is a crossing. Ties matter: at equal x, insert starts first, process verticals, then remove ends, so segments that merely touch still count.

The “Several crossings” preset finds 4 crossings, “Touching ends count” finds 2 (an end touching a segment counts), and “One vertical crosses all” finds 3. Visiting the active y-values in range costs O(log n) plus the number visited, so the whole sweep is O(n log n + k) for k crossings and is output-sensitive.

Java

1// horiz[i] = {y, x1, x2}; vert[i] = {x, y1, y2}; closed segments, touching counts
2static int crossings(int[][] horiz, int[][] vert) {
3    List<int[]> events = new ArrayList<>();                  // {x, kind, index}: 0 = horizontal starts, 1 = vertical, 2 = horizontal ends
4    for (int i = 0; i < horiz.length; i++) { events.add(new int[]{horiz[i][1], 0, i}); events.add(new int[]{horiz[i][2], 2, i}); }
5    for (int i = 0; i < vert.length; i++) events.add(new int[]{vert[i][0], 1, i});
6    events.sort((p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(p[1], q[1]));
7    TreeMap<Integer, Integer> activeY = new TreeMap<>();     // y -> number of active horizontal segments at that y
8    int count = 0;
9    for (int[] e : events) {
10        if (e[1] == 0) activeY.merge(horiz[e[2]][0], 1, Integer::sum);
11        else if (e[1] == 2) { if (activeY.merge(horiz[e[2]][0], -1, Integer::sum) == 0) activeY.remove(horiz[e[2]][0]); }
12        else {
13            for (int c : activeY.subMap(vert[e[2]][1], true, vert[e[2]][2], true).values()) count += c;
14        }
15    }
16    return count;
17}

Best

O(n log n)

Average

O(n log n + k)

Worst

O(n log n + k)

Space

O(n)

Counting crossings of horizontal and vertical segments

Interactive · edit the input

H1 y=2

[1, 6]

H2 y=4

[3, 9]

H3 y=7

[0, 4]

V1 x=3

y 0-5

V2 x=5

y 3-8

V3 x=8

y 1-9

0123456789

events by x (add, query, remove)

+H3@0

+H1@1

+H2@3

?V1@3

−H3@4

?V2@5

−H1@6

?V3@8

−H2@9

active y values

none

crossings found

none

Setup

Sweep a vertical line from left to right. A horizontal segment is active between its two end x values. When the sweep reaches a vertical segment, every active y inside its y-range is a crossing. At the same x, add first and remove last so touching ends count.

Step 1 / 11

Java

1static int crossings(int[][] horiz, int[][] vert) {            // horiz: {y, x1, x2}; vert: {x, y1, y2}
2    List<int[]> ev = new ArrayList<>();                         // {x, type, index}: 0 = add h-segment, 1 = vertical query, 2 = remove
3    for (int i = 0; i < horiz.length; i++) { ev.add(new int[]{horiz[i][1], 0, i}); ev.add(new int[]{horiz[i][2], 2, i}); }
4    for (int i = 0; i < vert.length; i++) ev.add(new int[]{vert[i][0], 1, i});
5    ev.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));   // at one x: add, query, then remove
6    TreeMap<Integer, Integer> ys = new TreeMap<>(); int count = 0;                                 // active y -> multiplicity
7    for (int[] e : ev) {
8        if (e[1] == 0) ys.merge(horiz[e[2]][0], 1, Integer::sum);
9        else if (e[1] == 2) { if (ys.merge(horiz[e[2]][0], -1, Integer::sum) == 0) ys.remove(horiz[e[2]][0]); }
10        else for (int c : ys.subMap(vert[e[2]][1], true, vert[e[2]][2], true).values()) count += c;   // active y inside the vertical range
11    }
12    return count;
13}

Live state

horizontal

vertical

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L2	horizontal=3 vertical=3	Sweep a vertical line from left to right. A horizontal segment is active between its two end x values. When the sweep reaches a vertical segment, every active y inside its y-range is a crossing. At the same x, add first and remove last so touching ends count.
2	L8	x=0 event=add H3	x = 0: horizontal segment H3 (y = 7) becomes active.
3	L8	x=1 event=add H1	x = 1: horizontal segment H1 (y = 2) becomes active.
4	L8	x=3 event=add H2	x = 3: horizontal segment H2 (y = 4) becomes active.
5	L10	x=3 query=V1 y 0..5 crossings=2	Vertical V1 spans y 0 to 5: the active values 2, 4 lie inside it, so 2 crossings (total 2).
6	L9	x=4 event=remove H3	x = 4: H3 ends and leaves the active set.
7	L10	x=5 query=V2 y 3..8 crossings=3	Vertical V2 spans y 3 to 8: the active values 4 lie inside it, so 1 crossing (total 3).
8	L9	x=6 event=remove H1	x = 6: H1 ends and leaves the active set.
9	L10	x=8 query=V3 y 1..9 crossings=4	Vertical V3 spans y 1 to 9: the active values 4 lie inside it, so 1 crossing (total 4).
10	L9	x=9 event=remove H2	x = 9: H2 ends and leaves the active set.
11	L12	return=4	4 crossings. The sweep costs O((n + k) log n) for n segments and k crossings reported.

22.05.3

Closest pair sweep

To find the closest pair among n points, sort by x and sweep. Keep an ordered set, sorted by y, of the points whose x is within the current best distance d of the sweep line. For each new point only the active points whose y lies within d need to be checked, and a packing argument shows there are at most a constant number of them (at most 6 points fit in the d × 2d box around the new point, since all pairs among active points are at least d apart).

So the sweep makes a few distance checks per point instead of comparing against all earlier ones. In the animation's “Classic” preset (5 points) it needs 1 distance check where brute force needs 10 pairs, finding the pair (3, 4) and (2, 3) at distance 1.414. “Vertical stack” needs 2 checks instead of 6, and “Grid” needs 3 instead of 10. Total cost is O(n log n) for the sort and the set operations.

Java

1// returns the squared distance of the closest pair; at least two points required
2static long closestPairSquared(int[][] points) {
3    int[][] p = points.clone();
4    Arrays.sort(p, Comparator.comparingInt(a -> a[0]));      // by x
5    TreeSet<int[]> active = new TreeSet<>((a, b) -> a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
6    long best = Long.MAX_VALUE;
7    int left = 0;
8    for (int i = 0; i < p.length; i++) {
9        long reach = (long) Math.ceil(Math.sqrt((double) best));      // current best distance, rounded up
10        while (left < i && (long) (p[i][0] - p[left][0]) * (p[i][0] - p[left][0]) >= best) active.remove(p[left++]);   // too far left
11        int d = (int) Math.min(reach, 1_000_000_000L);       // coordinates are assumed to stay well inside int range
12        for (int[] q : active.subSet(new int[]{Integer.MIN_VALUE, p[i][1] - d}, true, new int[]{Integer.MAX_VALUE, p[i][1] + d}, true)) {
13            long dx = p[i][0] - q[0], dy = p[i][1] - q[1];
14            best = Math.min(best, dx * dx + dy * dy);
15        }
16        active.add(p[i]);
17    }
18    return best;
19}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

Closest pair of points by a sweep line

Interactive · edit the input

points sorted by x

(2, 3)

(3, 4)

(5, 1)

(12, 10)

(12, 30)

(40, 50)

active strip (sorted by y)

none

Setup

Sweep left to right. The active strip holds the points whose x is closer than the best distance so far, ordered by y. A new point only needs to be compared with strip points whose y is also within the best distance: a constant number of them.

Step 1 / 14

Java

1static long closest(int[][] pts) {                                   // returns the smallest squared distance
2    Arrays.sort(pts, Comparator.comparingInt(p -> p[0]));            // sweep by x
3    TreeSet<int[]> active = new TreeSet<>(Comparator.<int[]>comparingInt(p -> p[1]).thenComparingInt(p -> p[0]));   // by y
4    long best = Long.MAX_VALUE; int left = 0;
5    for (int[] p : pts) {
6        while (left < pts.length && (long) (p[0] - pts[left][0]) * (p[0] - pts[left][0]) >= best) active.remove(pts[left++]);   // too far left
7        for (int[] q : active.subSet(new int[]{0, p[1] - (int) Math.sqrt(best) - 1}, new int[]{0, p[1] + (int) Math.sqrt(best) + 1})) {
8            long dx = p[0] - q[0], dy = p[1] - q[1];
9            best = Math.min(best, dx * dx + dy * dy);               // only points within the strip can improve it
10        }
11        active.add(p);
12    }
13    return best;
14}

Live state

0 distance checks

points

best

∞

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L3	points=6 best=∞	Sweep left to right. The active strip holds the points whose x is closer than the best distance so far, ordered by y. A new point only needs to be compared with strip points whose y is also within the best distance: a constant number of them.
2	L11	added=(2,3) strip=1	Add (2, 3) to the strip.
3	L9	p=(3,4) q=(2,3) squared distance=2 best=2	Distance² to (2, 3) is 2: a new best.
4	L11	added=(3,4) strip=2	Add (3, 4) to the strip.
5	L6	removed=(2,3) best=2	(2, 3) is at least √2 to the left of x = 5: it can never beat the best distance again, so it leaves the strip.
6	L6	removed=(3,4) best=2	(3, 4) is at least √2 to the left of x = 5: it can never beat the best distance again, so it leaves the strip.
7	L11	added=(5,1) strip=1	Add (5, 1) to the strip.
8	L6	removed=(5,1) best=2	(5, 1) is at least √2 to the left of x = 12: it can never beat the best distance again, so it leaves the strip.
9	L11	added=(12,10) strip=1	Add (12, 10) to the strip.
10	L11	added=(12,30) strip=2	Add (12, 30) to the strip.
11	L6	removed=(12,10) best=2	(12, 10) is at least √2 to the left of x = 40: it can never beat the best distance again, so it leaves the strip.
12	L6	removed=(12,30) best=2	(12, 30) is at least √2 to the left of x = 40: it can never beat the best distance again, so it leaves the strip.
13	L11	added=(40,50) strip=1	Add (40, 50) to the strip.
14	L13	return=2 distance=1.414 pair=(3,4) – (2,3)	Closest pair (3, 4) and (2, 3): squared distance 2, distance 1.414. 1 distance check instead of 15 for brute force.

22.05.4

Ordered event sets

Every two-dimensional sweep above relies on an **ordered set** that supports insert, delete and neighbour queries in O(log n). In Java that is TreeSet (a set) or TreeMap (keys with values). The operations worth knowing: first/last, floor/lower (largest key at most or below x), ceiling/higher (smallest key at least or above x), and subSet/subMap for a range.

A **multiset** (a collection that allows repeated values and removal of one copy) is built as a TreeMap from value to count, as in the skyline code: increment the count on insert and remove the key when it drops to zero. A PriorityQueue is not a substitute when you must delete an arbitrary element, because remove(Object) takes O(n).

Need	TreeSet / TreeMap method	Cost
Smallest / largest	first(), last() / firstKey(), lastKey()	O(log n)
Largest at most x	floor(x) / floorKey(x)	O(log n)
Smallest at least x	ceiling(x) / ceilingKey(x)	O(log n)
Everything in [a, b]	subSet / subMap, iterate	O(log n + k)
Remove one element	remove(x)	O(log n)

Java

1// multiset of ints on a TreeMap
2static void multisetAdd(TreeMap<Integer, Integer> ms, int v) { ms.merge(v, 1, Integer::sum); }
3
4static boolean multisetRemove(TreeMap<Integer, Integer> ms, int v) {
5    Integer c = ms.get(v);
6    if (c == null) return false;
7    if (c == 1) ms.remove(v); else ms.put(v, c - 1);
8    return true;
9}
10
11static Integer multisetMax(TreeMap<Integer, Integer> ms) { return ms.isEmpty() ? null : ms.lastKey(); }
12
13static Integer multisetFloor(TreeMap<Integer, Integer> ms, int v) { return ms.floorKey(v); }   // largest value <= v

Skyline: sweep with a multiset of heights

Interactive · edit the input

B1 h=10

[2, 9]

B2 h=15

[3, 7]

B3 h=12

[5, 12]

B4 h=10

[15, 20]

B5 h=8

[19, 24]

0123456789101112131415161718192021222324

events (x, ±height)

2:-10

3:-15

5:-12

7:15

9:10

12:12

15:-10

19:-8

20:10

24:8

active heights (max last)

outline key points

none

Setup

Each building gives a start event (negative height) and an end event. Sweep left to right, keeping every active height. Whenever the tallest active height changes, the outline has a key point.

Step 1 / 12

Java

1static List<int[]> skyline(int[][] b) {                         // b[i] = {left, right, height}
2    List<int[]> ev = new ArrayList<>();
3    for (int[] x : b) { ev.add(new int[]{x[0], -x[2]}); ev.add(new int[]{x[1], x[2]}); }   // start: negative height
4    ev.sort((p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(p[1], q[1]));
5    TreeMap<Integer, Integer> active = new TreeMap<>(); active.put(0, 1);               // height -> count; the ground
6    List<int[]> out = new ArrayList<>(); int prev = 0;
7    for (int[] e : ev) {
8        int h = Math.abs(e[1]);
9        if (e[1] < 0) active.merge(h, 1, Integer::sum);                                  // a building starts
10        else if (active.merge(h, -1, Integer::sum) == 0) active.remove(h);               // a building ends
11        int top = active.lastKey();                                                      // the tallest active building
12        if (top != prev) { out.add(new int[]{e[0], top}); prev = top; }                  // the outline changes here
13    }
14    return out;
15}

Live state

buildings

No condition evaluated on this step

Execution trace (dry run table)Show 12 steps

Step	Line	State	What happens
1	L2	buildings=5	Each building gives a start event (negative height) and an end event. Sweep left to right, keeping every active height. Whenever the tallest active height changes, the outline has a key point.
2	L12	x=2 event=start h=10 top=10 outline=1	At x = 2 a building of height 10 starts. The tallest active height is 10: it changed, so (2, 10) is a key point.
3	L12	x=3 event=start h=15 top=15 outline=2	At x = 3 a building of height 15 starts. The tallest active height is 15: it changed, so (3, 15) is a key point.
4	L12	x=5 event=start h=12 top=15 outline=2	At x = 5 a building of height 12 starts. The tallest active height is 15: unchanged, so the outline continues.
5	L12	x=7 event=end h=15 top=12 outline=3	At x = 7 a building of height 15 ends. The tallest active height is 12: it changed, so (7, 12) is a key point.
6	L12	x=9 event=end h=10 top=12 outline=3	At x = 9 a building of height 10 ends. The tallest active height is 12: unchanged, so the outline continues.
7	L12	x=12 event=end h=12 top=0 outline=4	At x = 12 a building of height 12 ends. The tallest active height is 0: it changed, so (12, 0) is a key point.
8	L12	x=15 event=start h=10 top=10 outline=5	At x = 15 a building of height 10 starts. The tallest active height is 10: it changed, so (15, 10) is a key point.
9	L12	x=19 event=start h=8 top=10 outline=5	At x = 19 a building of height 8 starts. The tallest active height is 10: unchanged, so the outline continues.
10	L12	x=20 event=end h=10 top=8 outline=6	At x = 20 a building of height 10 ends. The tallest active height is 8: it changed, so (20, 8) is a key point.
11	L12	x=24 event=end h=8 top=0 outline=7	At x = 24 a building of height 8 ends. The tallest active height is 0: it changed, so (24, 0) is a key point.
12	L14	return=[(2, 10), (3, 15), (7, 12), (12, 0), (15, 10), (20, 8), (24, 0)]	Skyline key points: [(2, 10), (3, 15), (7, 12), (12, 0), (15, 10), (20, 8), (24, 0)]. O(n log n): the sort plus O(log n) per event on the ordered multiset.

Practice ladder

Now try it yourself

Easy

Minimum Time Difference
Maximum Gap

Medium

Brick Wall
My Calendar III
Car Fleet

Advanced

The Skyline Problem
Rectangle Area II
Perfect Rectangle

Key takeaways

A vertical sweep line reduces a plane problem to events plus an ordered set of active objects.
The skyline keeps a multiset of active heights and reports a key point when the maximum changes.
Orthogonal intersections insert, query and remove the y-values of horizontal segments as the sweep passes them.
The closest pair needs only the points inside a window of the current best distance, so O(n log n) overall.
TreeMap and TreeSet supply floor, ceiling, range and multiset operations in O(log n).