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 -dimensional array. The
collision-checking is even performed in advance. Any cell that
contains at least one point in 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 as the Voronoi regions of a
collection of samples
in . The
``name'' of each cell corresponds uniquely to a sample in . The
cell that contains some is defined as the nearest sample in
, using some predetermined metric on . As a special case, the
cubical decomposition defines the cells based on a Sukharev grid
(recall Figure 5.5a). If the dimension of 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 (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 . If no solution is found for a
given , then the partition could be improved by adding more
samples. This allows any dense sequence to be used to guide the
exploration of while ensuring resolution completeness, which is
discussed next.

Steven M LaValle 2012-04-20