##

6.3.2 2D Decompositions

The vertical decomposition method of Section 6.2.2 is just
one choice of many cell decomposition methods for solving the problem
when
is polygonal. It provides a nice balance between the
number of cells, computational efficiency, and implementation ease.
It is usually possible to decompose
into far fewer convex
cells. This would be preferable for multiple-query applications
because the roadmap would be smaller. It is unfortunately quite
difficult to optimize the number of cells. Determining the
decomposition of a polygonal
with holes that uses the smallest
number of convex cells is NP-hard [519,645]. Therefore, we
are willing to tolerate nonoptimal decompositions.

**Subsections**

Steven M LaValle
2012-04-20