Complexity

How many cells can there possibly be in the worst case? First count the number of noncritical regions in $ {\mathbb{R}}^2$. There are $ O(n)$ different ways to generate critical curves of the first three types because each corresponds to a single feature. Unfortunately, there are $ O(n^2)$ different ways to generate bitangents and the Conchoid of Nicomedes because these are based on pairs of features. Assuming no self-intersections, a collection of $ O(n^2)$ curves in $ {\mathbb{R}}^2$, may intersect to generate at most $ O(n^4)$ regions. Above each noncritical region in $ {\mathbb{R}}^2$, there could be a cylinder of $ O(n)$ $ 3$-cells. Therefore, the size of the cell decomposition is $ O(n^5)$ in the worst case. In practice, however, it is highly unlikely that all of these intersections will occur, and the number of cells is expected to be reasonable. In [851], an $ O(n^5)$-time algorithm is given to construct the cell decomposition. Algorithms that have much better running time are mentioned in Section 6.5.3, but they are more complicated to understand and implement.

Steven M LaValle 2020-08-14