• What is Sweep Line?
• Events and Active Set
• 1D Interval Problems
• 2D Geometry: Intersections and Union
• Bentley–Ottmann for Segment Intersections
• Pitfalls and Robustness
• Exercises

Plane sweep processes geometric objects by moving a conceptual line (usually left→right) and handling events in sorted order while maintaining an active set of elements intersecting the sweep line.

• Core: event priority queue + balanced BST for active set
• Typical: O((n + k) log n) where k is number of reported events (e.g., intersections)
• Use cases: intersections, union area/length, rectangle cover, skyline, visibility

• Events: segment/rectangle start and end; intersection discovery.
• Active set: ordered by y at current x for line segments; by index for intervals.
• Neighbors: only adjacent items in the active set can create new intersections.

// Total covered length of intervals on a line
function totalCoveredLength(intervals) {
  const events = [];
  for (const [l, r] of intervals) {
    events.push([l, +1]);
    events.push([r, -1]);
  }
  events.sort((a,b) => a[0] - b[0] || a[1] - b[1]);
  let cov = 0, cnt = 0, prev = null;
  for (const [x, t] of events) {
    if (prev !== null && cnt > 0) cov += x - prev;
    cnt += t;
    prev = x;
  }
  return cov;
}

// Rectangle union area via vertical sweep (axis-aligned)
function rectangleUnionArea(rects) {
  // rect = [x1,y1,x2,y2]
  const events = [];
  const ys = new Set();
  for (const [x1,y1,x2,y2] of rects) {
    events.push([x1, +1, y1, y2]);
    events.push([x2, -1, y1, y2]);
    ys.add(y1); ys.add(y2);
  }
  const ysArr = [...ys].sort((a,b) => a - b);
  const idx = v => ysArr.findIndex(y => y === v);
  const cover = Array(ysArr.length * 4).fill(0);
  const length = Array(ysArr.length * 4).fill(0);
  function upd(node, l, r, ql, qr, val) {
    if (qr <= l || r <= ql) return;
    if (ql <= l && r <= qr) { cover[node] += val; push(node, l, r); return; }
    const m = (l + r) >> 1;
    upd(node*2, l, m, ql, qr, val);
    upd(node*2+1, m, r, ql, qr, val);
    length[node] = cover[node] > 0 ? ysArr[r] - ysArr[l] : length[node*2] + length[node*2+1];
  }
  function push(node, l, r) {
    if (cover[node] > 0) length[node] = ysArr[r] - ysArr[l];
    else if (r - l > 1) length[node] = length[node*2] + length[node*2+1];
    else length[node] = 0;
  }
  events.sort((a,b) => a[0] - b[0]);
  let prevX = events[0]?.[0] ?? 0, area = 0;
  for (const [x, t, y1, y2] of events) {
    area += (x - prevX) * length[1];
    upd(1, 0, ysArr.length - 1, idx(y1), idx(y2), t);
    prevX = x;
  }
  return area;
}

Reports all intersections among N line segments in O((n + k) log n) using an event queue (segment endpoints and discovered intersections) and an ordered active set. New intersections only occur between neighbors after swaps.

• Degeneracies: overlapping segments, shared endpoints; define tie-breaking.
• Numeric robustness: prefer exact arithmetic for comparisons; handle EPS.
• Event ordering: process removals before insertions at same x when needed.

1. Compute the union length of many intervals with overlaps.
2. Count intersections among axis-aligned segments using sweep + active set.
3. Implement skyline problem (building outline) via sweep and heap.