Finding all possible reflection matrices for a given Wythoff construction

Question

As a pet project, I'm trying to build a small app that visualizes 4D polytopes. I want to use the Wythoff Construction method, where the shape is generated kaleidoscopically by the interaction of 4 mirrors using a single movable generator vertex.

I know how to create a reflection matrix from a hypersurface normal, what I am looking for is an simple way to generate all possible matrices generated by the interreflections of the set of mirrors.

The brute force method would be something like:

1: Create the initial set of mirrors and their matrices
2: Reflect each matrix in each of the other mirrors, add to temp list
3: Remove duplicates from temp list
4: Add temp list to master list and remove duplicates
5: Reflect each matrix in temp list through each mirror except its generating mirror 
   and add to new temp list
6: Repeat from step 3 with new temp list, continue until no non-duplicates found

This method will work but will involve a huge amount of redundant computation generating, checking, and discarding duplicates, especially in symmetry groups like the 120-cell / 600-cell which contain thousands of permutations. Does anybody know of a more elegant method of creating the full set?

Answer 1

I found an answer in the form of the Todd-Coxeter Algorithm from group theory. This still involves iterating over permutations of the group, and removing duplicates. However, the group can be defined using symbols to represent different sequences of operations, and duplicate-matching performed on these symbols rather than elements of the group itself.

For example, if a pair of mirrors A and B have an angle of (PI/3) then they form a cycle of order 3 (since a reflection through a pair of mirrors equals a rotation through twice the angle between them). So the sequence ABABAB maps any element back onto itself. By constructing a path like this for each pair of mirrors, it's possible to define new elements for each step along a path, then eliminate duplicates either through string-matching operations or by constructing a graph and eliminating equivalent nodes. For large sets, this should be much more efficient than multiplying and comparing matrices directly at each step.