Additional implications?

[origamimagiro]

After initial crease assignment and implications, there may be a way to infer more variables:

• compile all one-step inferences for the assignment of both 1 and 2 for each unassigned variable v
• if another variable v' is implied with:
  • a different value for the same assignment of v, it is a contradiction the opposite assignment of v can be inferred
  • the same value for both assignments of v, v' can be inferred as that value
  • a different value for both assignments of v, v and v' are linked (i.e., if one is assigned, the assignment of the other is also known)
    Perhaps can use these links to order which variables to guess first, guessing variables in larger linked components first.

[origamimagiro]

The hope was that such inferences would be able to identify some variables that were not inferred from the current method, enabling the identification and separation of additional connected components. However, I implemented the above checks and was unable to find any additional variable assignments beyond those that were already inferred, for any of the crease patterns in my test set. :(

That said, there are still cases where independent components are not separated by the current algorithm. Consider the following crease pattern. There are three sets of variables, each with two valid assignments, whose choice of assignment are independent from one another, resulting in $8 = 2^3$ states. However, they overlap in a way so as to remain linked in the constraint graph using the current separation algorithm. How can we identify such separable components?

The current algorithm removes variables from the graph after they have been assigned, but my guess is that it is possible to identify and remove some constraints from the graph, even if they are still connected to some unassigned variables, as long as they no longer constrain those variables.

[OrigamiDraw]

To better understand what is going on, I made cross sections of the 8 different states:

We can see how we would like to separate this in 3 different components.

[origamimagiro]

I have finally figured out how to remove redundant constraints to make the above example separable!

First, I note that transitivity constraints are very weak, only limiting triplets of faces from having a cyclic order, which does not occur very often. However, there can be $\Omega(n^3)$ transitivity constraints, so for many crease patterns, they are by far the largest part of the constraint graph (by contrast, there are only ever at most $O(n^2)$ constraints of the all other types).

That said, many transitivity constraints may be implied by other constraints and can be removed. For example, currently, flat-folder removes transitivity constraints that are directly implied by taco-tortilla or taco-taco constraints. Specifically:

• For taco-tortilla constraint A(BC), where a face A overlaps an edge connecting faces B and C, the transitivity constraint ABC between faces A, B, and C is implied and may be removed, as the taco-tortilla constraint is strictly more restrictive.
• Similarly for taco-taco constraint (AB)(CD), where an edge between faces A and B overlaps an edge between faces C and D, the transitivity constraints {ABC, ABD, ACD, BCD} are all implied and may be removed.

Interestingly, there are even more transitivity constraints that can be implied by groups of taco-tortilla constraints, which, when removed, may disconnect the constraint graph even further (as is the case in the above example).

• Consider two taco-tortilla constraints X(AB) and X(BC). Then as discussed above, transitivity constraints XAB and XBC are implied and may be removed.
• But note that, since these constraints imply that face X is neither between faces A and B nor between faces B and C, face X must exist either above or below all of faces ABC. In particular, X cannot form a cycle with faces A and C, so the transitivity constraint XAC is also implied and may be removed.

In particular, if you apply this transitivity removal rule repeatedly to the constraint graph for the example above, the unassigned part of the constraint graph is no longer fully connected, and decomposes into 3 independently assignable components, each admitting 2 valid states as desired. This filter should hopefully significantly reduce the number of transitivity constraints that need to be considered, and hopefully speed up state solving for many examples.

Currently, the easiest place to add this filter is at the same place we are currently filtering transitivity constraints (at the end of BF_EF_ExE_ExF_BT3_2_BT0_BT1_BT2 in conversion.js). An algorithm to identify and remove such transitivity constraints could be as follows:

• Partition all taco-tortilla constraints into groups according to their tortilla face.
• For each tortilla face X with partition group P:
  • Construct graph G
    • For each constraint X(AB) in P
      • Construct an undirected graph edge (A,B) connecting faces A and B
  • For each connected component C of G
    • For each pair of faces A, B in C
      • Remove transitivity constraint XAB

I'm not sure by how much this will decrease the size of the constraint graph, but because this filter could in theory remove $\Omega(n^3)$ transitivity constraints, it has the potential to decease the number of transitivity constraints significantly. As a small optimization, perhaps we should consider computing these implied transitivity constraints first, before computing the unfiltered transitivity constraints, but not so important as that wouldn't change the asymptotic worst-case running time.

[origamimagiro]

Implemented in commit d7d1cf2.