Scanline / Event Processing

Scanline technique also known as Sweep Line

Introduction

Imagine a line moving from left to right and scanning everything it passes. This moving line is called a scanline. In a one-dimensional problem, we can imagine a point moving along the number line instead, but the idea is the same: we move from left to right and remember the current state.

At first, it may seem that we should stop at every possible coordinate. However, the state is usually unchanged for long stretches. If no interval starts or ends between $x=3$ and $x=8$, then exactly the same intervals are active everywhere between these coordinates. Checking all those points would repeat the same work.

Instead, the scanline jumps directly to the important positions. A position where the state changes is called an event. Sometimes we also create an event at a position where we need to read the current state, such as the position of a query.

Thus, an event is simply a small record that tells us:

• where the scanline should stop;
• what should happen at that position;
• any additional information needed to process it.

We create all events, sort them from left to right, and process them in that order. Between two consecutive events, nothing relevant happens, so the scanline can skip that entire part.

Problem or motivation

You are given $n$ closed intervals and query points . For every query point, find how many intervals contain it.