To handle motion planning queries, a roadmap is constructed from the
vertical cell decomposition. For each cell , let denote a
designated *sample point* such that
. The sample points can be selected as the cell
centroids, but the particular choice is not too important. Let
be a topological graph defined as follows. For every
cell, , define a vertex . There is a vertex for every
1-cell and every 2-cell. For each 2-cell, define an edge from its
sample point to the sample point of every 1-cell that lies along its
boundary. Each edge is a line-segment path between the sample points
of the cells. The resulting graph is a roadmap, as depicted in Figure
6.4. The accessibility condition is satisfied because
every sample point can be reached by a straight-line path thanks to
the convexity of every cell. The connectivity condition is also
satisfied because is derived directly from the cell
decomposition, which also preserves the connectivity of
.
Once the roadmap is constructed, the cell information is no longer
needed for answering planning queries.

Steven M LaValle 2012-04-20