#### 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 to , using to denote a point in .

From Section 6.2.1, note that the set of vertices are the only data in that appear in the problem input. It therefore seems reasonable that interesting things can only occur at these points. Sort the points in in increasing order by their coordinate. Assuming general position, no two points have the same coordinate. The points in will now be visited in order of increasing value. Each visit to a point will be referred to as an event. Before, after, and in between every event, a list, , of some 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.

Steven M LaValle 2012-04-20