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