Now we are prepared to explain the cell decomposition in more detail.
Imagine traveling along a path in
and producing an animated
version of the radar map in Figure 6.22b. We say that a
*critical change* occurs each time the circular ordering
representation of (6.6) changes. Changes occur when
intervals: 1) appear, 2) disappear, 3) split apart, 4) merge into one,
or 5) when the feature of an interval changes. The first task is to
partition
into maximal -cells over which no critical
changes occur. Each one of these -cells, , represents the
projection of a strip of -cells in
. Each -cell is
defined as follows. Let
denote the 3D region in
for which
and places the segment
between contacts and . The *cylinder* of cells above is given by
for each interval in the circular ordering
representation, (6.6). If any orientation is possible
because never contacts an obstacle while in , then we write
.

What are the positions in
that cause critical changes to
occur? It turns out that there are five different cases to consider,
each of which produces a set of *critical curves* in
.
When one of these curves is crossed, a critical change occurs. If
none of these curves is crossed, then no critical change can occur.
Therefore, these curves precisely define the boundaries of the desired
-cells in
. Let denote the length of the robot (which
is the line segment).

Consider how the five cases mentioned above may occur. Two of the five cases have already been observed in Figures 6.22 and 6.23. These appear in Figures 6.24a and Figures 6.24b, and occur if is within of an edge or a vertex. The third and fourth cases are shown in Figures 6.24c and 6.24d, respectively. The third case occurs because crossing the curve causes to change between being able to touch and being able to touch . This must be extended from any edge at an endpoint that is a reflex vertex (interior angle is greater than ). The fourth case is actually a return of the bitangent case from Figure 6.10, which arose for the shortest path graph. If the vertices are within of each other, then a linear critical curve is generated because is no longer able to touch when crossing it from right to left. Bitangents always produce curves in pairs; the curve above is not shown. The final case, shown in Figure 6.25, is the most complicated. It is a fourth-degree algebraic curve called the Conchoid of Nicomedes, which arises from being in simultaneous contact between and . Inside of the teardrop-shaped curve, can contact but not . Just outside of the curve, it can touch . If the coordinate frame is placed so that is at , then the equation of the curve is

in which is the distance from to .

Putting all of the curves together generates a cell decomposition of
. There are *noncritical regions*, over which there is no
change in (6.6); these form the -cells. The
boundaries between adjacent -cells are sections of the critical
curves and form -cells. There are also 0-cells at places where
critical curves intersect. Figure 6.26 shows an example
adapted from [588]. Note that critical curves are not drawn if
their corresponding configurations are all in
. The method
still works correctly if they are included, but unnecessary cell
boundaries are made. Just for fun, they could be used to form a nice
cell decomposition of
, in addition to
. Since
is avoided, is seems best to avoid wasting time on decomposing it.
These unnecessary cases can be detected by imagining that is a
laser with range . As the laser sweeps around, only features that
are contacted by the laser are relevant. Any features that are hidden
from view of the laser correspond to unnecessary boundaries.

After the cell decomposition has been constructed in , it needs to be lifted into . This generates a cylinder of -cells above each 2D noncritical region, . The roadmap could easily be defined to have a vertex for every -cell and -cell, which would be consistent with previous cell decompositions; however, vertices at -cells are not generated here to make the coming example easier to understand. Each -cell, , corresponds to the vertex in a roadmap. The roadmap edges connect neighboring -cells that have a -cell as part of their common boundary. This means that in they share a one-dimensional portion of a critical curve.

Steven M LaValle 2012-04-20