For either $ {\cal W}= {\mathbb{R}}^2$ or $ {\cal W}= {\mathbb{R}}^3$, it is possible to discretize a bounded portion of the world into rectangular cells that may or may not be occupied. The resulting model looks very similar to Example 2.1. The resolution of this discretization determines the number of cells per axis and the quality of the approximation. The representation may be considered as a binary image in which each ``1'' in the image corresponds to a rectangular region that contains at least one point of $ {\cal O}$, and ``0'' represents those that do not contain any of $ {\cal O}$. Although bitmaps do not have the elegance of the other models, they often arise in applications. One example is a digital map constructed by a mobile robot that explores an environment with its sensors. One generalization of bitmaps is a gray-scale map or occupancy grid. In this case, a numerical value may be assigned to each cell, indicating quantities such as ``the probability that an obstacle exists'' or the ``expected difficulty of traversing the cell.'' The latter interpretation is often used in terrain maps for navigating planetary rovers.

Steven M LaValle 2012-04-20