Wednesday, August 27, 2008

Overlap Program Description

By the Continuity Theorem (see previous posts), the migration operation spans all linear sidedness spaces, starting from any one. Similarly, migrations are sufficient to find all simplex overlaps of a given dimension. I need only check each migration from each overlap found so far, and find if it is equivalent to one found already. To simplify the equivalence check, I will impose an ordering on equivalent sections and remember only the first in order. The program to do this is described in the following.

Start with a single entry list. Finding this initial overlap example is the most difficult part of the program. Create the example overlap by modifying an overlap with one fewer boundary than desired. First choose a boundary. Then choose a boundary in the section by it. In the one dimensional case, choose a region and divide it by a new boundary. In the next dimension up, divide regions by a new boundary close to the chosen one, passing through the new boundary in the previous dimension. Continue up to the original dimension.

One question is whether the above method could be used to find all overlaps without using migrations. This would be less efficient than using migrations as below, because the above method would find all possible sidedness relations. The migration method below finds all overlaps while going through only some of the possible sidedness relations.

Now fill out the list with a representative from each overlap equivalence class. For each overlap in the growing list, for each possible migration, consider the resultant overlap. If the overlap is not equivalent to any on the list, then add it to the end of the list.

Determine equivalence by keeping a list of sections which compare as the least of all permutations and inversions. By definition, the equivalence class is all permutations and inversions. A one to one mapping is a permutation. An inversion is a reversal of all bits in the sidedness relation indexed by a boundary.