What if two points along
lie on a vertical line that slices
through
? What happens when one of the edges of
is
vertical? These are special cases that have been ignored so far.
Throughout much of combinatorial motion planning it is common to
ignore such special cases and assume
is in *general
position*. This usually means that if all of the data points are
perturbed by a small amount in some random direction, the probability
that the special case remains is zero. Since a vertical edge is no
longer vertical after being slightly perturbed, it is not in general
position. The general position assumption is usually made because it
greatly simplifies the presentation of an algorithm (and, in some
cases, its asymptotic running time is even lower). In practice,
however, this assumption can be very frustrating. Most of the
implementation time is often devoted to correctly handling such
special cases. Performing random perturbations may avoid this
problem, but it tends to unnecessarily complicate the solutions. For
the vertical decomposition, the problems are not too difficult to
handle without resorting to perturbations; however, in general, it is
important to be aware of this difficulty, which is not as easy to fix
in most other settings.

Steven M LaValle 2012-04-20