Maintaining the cells

There are several alternatives for maintaining the cells. The main operation that needs to be performed efficiently is point location [264]: determine which cell contains a given state. The original method in [73] preallocates an $n$-dimensional array. The collision-checking is even performed in advance. Any cell that contains at least one point in ${X_{obs}}$ can be labeled as occupied. This allows cells that contain collision configurations to be avoided without having to call the collision detection module. For a fixed dimension, this scheme finds the correct cell and updates the labels in constant time. Unfortunately, the space requirement is exponential in dimension.

An alternative is to use a hash table to maintain the collection of cells that are labeled as visited. This may be particularly valuable if optimality is not important and if it is expected that solutions will be found before most of the cells are reached. The point location problem can be solved efficiently without explicitly storing a multi-dimensional array.

Suppose that the cubical decomposition is not necessarily used. One general approach is to define ${\cal D}$ as the Voronoi regions of a collection $P$ of $m$ samples $\{p_1,\ldots,p_m\}$ in $X$. The ``name'' of each cell corresponds uniquely to a sample in $P$. The cell that contains some $x \in X$ is defined as the nearest sample in $P$, using some predetermined metric on $X$. As a special case, the cubical decomposition defines the cells based on a Sukharev grid (recall Figure 5.5a). If the dimension of $X$ is not too high, then efficient nearest-neighbor schemes can be used to determine the appropriate cell in near-logarithmic time in the number of points in $P$ (in practice, Kd-trees, mentioned in Section 5.5.2, should perform well). For maintaining a cubical decomposition, this approach would be cumbersome; however, it works for any sample set $P$. If no solution is found for a given $P$, then the partition could be improved by adding more samples. This allows any dense sequence to be used to guide the exploration of $X$ while ensuring resolution completeness, which is discussed next.