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.