Theorem 2: Out of all solutions to the set of constraints S, the instantiations of solve constraints( S ) have the fewest number of different values of od( a, b ), where a, b range over the symbols in S . This number is given by num labels( S ).

The proof is given in the appendix.

## 6. Extensions And Consequences

We next present a number of modifications of the algorithm solve constraints.  The first is a more efficient implementation. The second extends the algorithm to handle non-strict comparisons.  The third extend the algorithm to handle a combination of order-of-magnitude comparisons on distance with order comparisons, in a one-dimensional space.

## 6.1 An Efficient Implementation Of Solve_Constraints

It is possible to implement algorithm solve constraints somewhat more efficiently than the naive encoding of the above description. The key is to observe that the graph H of connected components does not have to be computed explicitly; it suffices to compute it implicitly using merge-find sets (union-find sets).  Combining this with suitable back pointers from edges to constraints, we can formulate a more efficient version of the algorithm.

We use the following data structures and subroutines:

- Each node N of the cluster tree contains pointers to its parents and children; a field N .label, holding the integer label; a field N .symbols, holding the list of symbols in the leaves of N ; and a field N .mfsets, holding a list of the connected components of the symbols in N . As described below, each connected component is implemented as an merge-find set (MFSET).

- An edge E in the graph over symbols contains its two endpoints, each of which is a symbol; a field E .shorts, a list of the constraints in which E appears as a short; and a field E longs, a list of the constraints in which E appears as a long.

- A constraint C has two fields, C .short and C .long, both of them edges. It also has pointers into the lists C .short.shorts and C .long.longs, enabling C to be removed in constant time from the constraint lists associated with the individual edges.

- We will use the disjoint-set forest implementation of MFSETs (Cormen, Leiserson, and Rivest, 1990, p. 448) with merging smaller sets into larger and path-compression.

Thus, each MFSET is a upward-pointing tree of symbols, each node of the tree being a symbol. The tree as a whole is represented by the symbol at the root. A symbol A
has then the following fields:
- A parent is a pointer to the parent in the MFSET tree.

- A cluster_leaf is a pointer to the leaf in the cluster tree containing A .

- If A is the root of the MFSET then A .size holds the size of the MFSET.

- If A is the root of the MFSET, then A symbols holds all the elements of the MFSET.