Geometric Uniqueness

Two geometric configurations are congruent if one can be transformed into the other by a translation and a rotation. We have shown in the section on the correctness of the algorithm that the reduction sequence, and hence the cluster formation, cannot interfere with termination or uniqueness of the normal form. But each reduction implies a geometric construction that places three clusters, by placing the three associated geometric configurations with respect to each other. Since these constructions have more than one solution, it is not at all evident whether different reduction sequences will produce congruent solutions. However, we will show that this is the case for all graphs that are not structurally overconstrained.

In our discussion of solution selection, we explained that heuristic rules are used to select one among several possible solutions in each construction step. The three elements whose relative orientation is preserved correspond to the graph nodes that are the pairwise intersections of a triple of clusters merged in a reduction step. It turns out that two different reduction sequences make use of the same set of triples. By Lemma 3, it is clear that in a set of clusters C the same triple of nodes cannot be used for two different reductions.

Definition 7
Let g1, g2, and g3 be the three geometric elements corresponding to the shared nodes when merging the clusters S1, S2, and S3. Denoting the reduction with r, we call the triadic set 
        g(r) = {g1, g2, g3}
the geometry triple of r
Definition 8
Let C be a set of clusters and t be a sequence of reductions applied to C. Then the set 
        TC(t) = {g(r): r is in t}
is the set of geometry triples, of C under t.
Theorem 6
Let G be a constraint graph that is not structurally overconstrained, and assume that CG ->* C. Let t1 and t2 be two reduction sequences that reduce C to normal form Cf. Then TC(t1) = TC(t2).
Proof:

By Corollary 5, C has a unique normal form Cf. Moreover, it is clear from Theorem 4 that the reduction sequences t1 and t2 must have the same length. Consequently, the sets TC(t1) and TC(t2) have equal cardinality. We proceed by induction on the length of t1.

Basis: t1 is a single reduction.

By Theorem 4, t1 = t2, so TC(t1) = TC(t2).

Induction Step: Assume that the theorem is true for reduction sequences of length n.

Let | t1 | = | t2 | = n + 1. Let CG ->* C, C ->t1 Cf, and C ->t2 Cf. 

                             
      Figure 1: Only one reduction can be applied to C
Case 1:

If t1 = s (t1*) and t2 = s (t2*) where s is a single reduction, then the theorem follows from the induction hypothesis applied to C', where C ->s C' and the sequences t1* and t2* take C' to Cf. A diagram of this situation is shown in Figure 1.

Case 2:

Let t1 = s (t1*) and t2 = r (t2*) where s and r are single reductions. Let C ->s Cs and C ->r Cr By Theorem 4, s and r commute, so there is a cluster set C' such that 

        C ->s Cs ->r C' 
        C ->r Cr ->s C'
Let t3 be any sequence that reduces C' to normal form. Figure 2 displays the flow of reductions. 
                             
      Figure 2: Two or more reductions applies to C
Applying the induction hypothesis to Cs and the sequences t1* and r t3, we have 
        TCs(t1*) = TCs(r t3) = TC'(t3) U {g(r)}
Similarly, applying the induction hypothesis to Cr and the sequences t2* and s t3, we have 
        TCr(t2*) = TCr(s t3) = TC'(t3) U {g(s)}
But then 
        TC(t1) = TCs(t1*) U {g(s)}
               = TC'(t3)  U {g(s)} U {g(r)}
               = TCr(t2*) U {g(r)}
               = TCt2
Lemma 7
Let G be structurally well-constrained. Assume that there are two reduction sequences t1 s r t2 and t1 r s t2 of CG to normal form Then the solutions constructed by the two sequences are congruent.
Proof:

Assume that 

        CG ->t1 C ->rs C1
        CG ->t1 C ->sr C2
We know that C1 and C2 are the same set of geometric elements. We prove that the corresponding geometric clusters in C1 and C1, constructed by rs and by sr are congruent. From the proof of Theorem 4, we only consider the cases where r and s involve five or six clusters. It is clear that in the case of six clusters C1 and C2 corresponding geometric clusters of are congruent.

Assume, next, that s merges S11, S12, and S13, and that r merges S11, S22, and S23. We may consider S11 fixed, so that s and r determine only the positions of g1 = S12 ^ S13 and g2 = S22 ^ S23, followed by translations and rotations of the geometric clusters of S12, S13, S22, and S23. Clearly, g1 and g2 are different and are therefore placed independently. By Theorem 6, the placement of gi is unique. Moreover, the placement of the geometric clusters of S12 and S13 is independent of the placement of the geometric clusters of S22 and S23, since S11 is fixed and G is not structurally overconstrained. Hence the geometric clusters of C1 must be congruent to the corresponding geometric clusters of C2.

Theorem 8
Let G be well-constrained; then the solutions constructed by two different reduction sequences leading to normal form are congruent.
Proof:

Let the two sequences be t1 and t2. By Theorem 4, we know that the two sequences are permutations of each other. The theorem now follows from Lemma 7 by induction on the number of transpositions of commuting reductions needed to change t1 into t2.

Theory