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.