Crease patterns with holes.

[origamimagiro]

Flat-Folder allows crease patterns to have holes (support for which has been recently improved with #38). However, it is worth noting that, for crease patterns with holes, Flat-Folder does not check whether found folded states are reachable without intersection. For example, for the following crease pattern, flat-folder finds four valid states, even though only two are reachable from the unfolded state without self-intersection.

I'm not sure the algorithmic complexity of deciding whether a state is reachable (not that it's particularly high on the priority list anyway), but adding here in case people have thoughts.

[edemaine]

I've worked on this some. (It's an open problem in this paper proving universality for no holes.) One obvious necessary condition is that the continuous transformation must be possible topologically, i.e., dropping the isometry constraint and just requiring no self intersection. I'm not sure how hard that topological problem is, but I assume it's at least as hard as the unknotting problem which whose best upper bound is NP ∩ coNP. It would be nice to prove equivalence...