Figure 6.22b illustrates which values of produce collision. We will refer to this representation as a radar map. The four contact orientations are indicated by the contact feature. The notation and identifies the two intervals for which . Now imagine changing by a small amount, to obtain . How would the radar map change? The precise angles at which the contacts occur would change, but the notation and , for configurations that lie in , remains unchanged. Even though the angles change, there is no interesting change in terms of the contacts; therefore, it makes sense to declare and to lie in the same cell in because and both place the segment between the same contacts. Imagine a column of two -cells above a small area around . One -cell is for orientations in , and the other is for orientations in . These appear to be 3D regions in because each of , , and can be perturbed a small amount without leaving the cell.

Of course, if is changed enough, then eventually we expect a dramatic change to occur in the radar map. For example, imagine is infinitely long, and the value is gradually increased in Figure 6.22a. The black band between and in Figure 6.22b shrinks in length. Eventually, when the distance from to is greater than the length of , the black band disappears. This situation is shown in Figure 6.23. The change is very important to notice because after that region vanishes, any orientation between and , traveling the long way around the circle, produces a configuration . This seems very important because it tells us that we can travel between the original two cells by moving the robot further way from , rotating the robot, and then moving back. Now move from the position shown in Figure 6.23 into the positive direction. The remaining black band begins to shrink and finally disappears when the distance to is further than the robot length. This represents another critical change.

The radar map can be characterized by specifying a circular ordering

 (6.6)

when there are orientation intervals over which the configurations lie in . For the radar map in Figure 6.22b, this representation yields . Each is a feature, which may be an edge or a vertex. Some of the may be identical; the representation for Figure 6.23b is . The intervals are specified in counterclockwise order around the radar map. Since the ordering is circular, it does not matter which interval is specified first. There are two degenerate cases. If for all , then we write for the ordering. On the other hand, if for all , then we write .

Steven M LaValle 2012-04-20