Completeness

To show that the algorithm is complete (i.e., that it finds a plan for any polygon) we must show that for any polygon, we can continue to grow the preimage until , or equivalently,

Theorem. For any polygonal part, we can always find a plan to orient the part up to symmetry.

Proof: As described earlier, any polygonal part will generate a squeeze function where all step widths have positive measure and . All values are taken modulo . We prove the claim by showing that for any squeeze function, we can always find a sequence of sets such that: the first set contains only a single point, each set is strictly larger than the previous set, for each pair of adjacent sets there exists an action such that , and the last set corresponds to a period of symmetry in the step function.

The trick is to show that for any set we can always find a way to generate a larger set (unless the set corresponds to a period of symmetry in the step function). We show that for any squeeze function and any ,

Either we can find a larger preimage:

Or is a period of symmetry in the squeeze function:

where the quantifiers range over the interval .

To understand formula (3), consider that we've reached a point in the algorithm where the current set is . Formula (3) says that there is some set, , larger than , whose image, , is smaller than . We can also interpret this with reference to Figure 7. Formula (3) says that we can always find a position for the lower left hand corner of the box such that the squeeze function enters on the left edge of the box and exits on the right edge.

To show that for any squeeze function and any , either (3) or (4) must hold, consider the integral of the function over the domain .

Since this integral is zero, then by the mean value theorem, either the function is uniformly zero (formula 4, i.e. ) or there is some point in the domain where the function is less than zero (formula 3).

Hence we can always continue to find larger sets until we reach a period of symmetry in the step function. We have shown earlier that we can transform this sequence of sets into a plan to orient the part up to symmetry. This proves the claim.