Cylindrical decomposition

The cylindrical decomposition is very similar to the vertical decomposition, except that when any of the cases in Figure 6.2 occurs, then a vertical line slices through all faces, all the way from $y = -\infty$ to $y = \infty$. The result is shown in Figure 6.18, which may be considered as a singular complex. This may appear very inefficient in comparison to the vertical decomposition; however, it is presented here because it generalizes nicely to any dimension, any C-space topology, and any semi-algebraic model. Therefore, it is presented here to ease the transition to more general decompositions. The most important property of the cylindrical decomposition is shown in Figure 6.19. Consider each vertical strip between two events. When traversing a strip from $y = -\infty$ to $y = \infty$, the points alternate between being ${\cal C}_{obs}$ and ${\cal C}_{free}$. For example, between events $4$ and $5$, the points below edge $f$ are in ${\cal C}_{free}$. Points between $f$ and $g$ lie in ${\cal C}_{obs}$. Points between $g$ and $h$ lie in ${\cal C}_{free}$, and so forth. The cell decomposition can be defined so that 2D cells are also created in ${\cal C}_{obs}$. Let $S(x,y)$ denote the logical predicate (3.6) from Section 3.1.1. When traversing a strip, the value of $S(x,y)$ also alternates. This behavior is the main reason to construct a cylindrical decomposition, which will become clearer in Section 6.4.2. Each vertical strip is actually considered to be a cylinder, hence, the name cylindrical decomposition (i.e., there are not necessarily any cylinders in the 3D geometric sense).

Figure 6.18: The cylindrical decomposition differs from the vertical decomposition in that the rays continue forever instead of stopping at the nearest edge. Compare this figure to Figure 6.6.

Figure 6.19: The cylindrical decomposition produces vertical strips. Inside of a strip, there is a stack of collision-free cells, separated by ${\cal C}_{obs}$.