Worst-Case Computational Complexity

We define the complexity of the algorithm as a function of the geometric complexity of the input, in this case the number of part vertices, . We neglect the numerical complexity of representing vertices and angles as rational numbers.

Step 1 (computing the squeeze function) can be performed in time [6]. Step 3 runs in time . To see this, note that we only need to consider positioning the box flush with each step and there are steps. We only need iterations of Step 3, since intervals can be constructed from continuous subsequences of the steps in the squeeze function. Thus the algorithm runs in time and finds plans of length .