Plane-sweep principle

The algorithm is based on the plane-sweep (or line-sweep) principle from computational geometry [129,264,302], which forms the basis of many combinatorial motion planning algorithms and many other algorithms in general. Much of computational geometry can be considered as the development of data structures and algorithms that generalize the sorting problem to multiple dimensions. In other words, the algorithms carefully ``sort'' geometric information.

The word ``sweep'' is used to refer to these algorithms because it can be imagined that a line (or plane, etc.) sweeps across the space, only to stop where some critical change occurs in the information. This gives the intuition, but the sweeping line is not explicitly represented by the algorithm. To construct the vertical decomposition, imagine that a vertical line sweeps from $x = -\infty$ to $x=\infty$, using $(x,y)$ to denote a point in ${\cal C}= {\mathbb{R}}^2$.

From Section 6.2.1, note that the set $P$ of ${\cal C}_{obs}$ vertices are the only data in ${\mathbb{R}}^2$ that appear in the problem input. It therefore seems reasonable that interesting things can only occur at these points. Sort the points in $P$ in increasing order by their $X$ coordinate. Assuming general position, no two points have the same $X$ coordinate. The points in $P$ will now be visited in order of increasing $x$ value. Each visit to a point will be referred to as an event. Before, after, and in between every event, a list, $L$, of some ${\cal C}_{obs}$ edges will be maintained. This list must be maintained at all times in the order that the edges appear when stabbed by the vertical sweep line. The ordering is maintained from lower to higher.