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 ${\cal C}_{obs}$ is polygonal. It provides a nice balance between the number of cells, computational efficiency, and implementation ease. It is usually possible to decompose ${\cal C}_{obs}$ 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 ${\cal C}_{obs}$ with holes that uses the smallest number of convex cells is NP-hard [519,645]. Therefore, we are willing to tolerate nonoptimal decompositions.