for i = 1 . . p do G[Cj] := x, instantiate1( C i ,  Ω , δ 1  . . δ k ,  G );
end for endif end instantiatel Thus, we begin by picking orders of magnitude corresponding to the values of the labels.

We pick an arbitrary point for the root of the tree, and then recurse down the nodes of the tree. For each node N, we place the children at points that all lie separated by the desired diameter of N . The final placement of the leaves is then the desired instantiation.

Lemma 2: If T is a cluster tree and Ω is an om-space, then instantiate(T, Ω) returns an instantiation of T
The proof is given in the appendix. Moreover, it is clear that any instantiation Γ of Γ can be generated as a possible output of instantiate( T , Ω).  (Given an instantiation Γ , just pick G [ N ] at each stage to be Γ of some symbol of N .)
Note that, given any valuation Γ over a finite set of symbols S, there exists a cluster tree T su that T symbols = S and Γ satisfies T . Su a T is essentially unique up to an isomorphism over the set of labels that preserves the label 0 and the order of labels.

## 5. Constraints

In this section, we develop the first of our algorithms. Algorithm solve constraints tests a collection of constraints of the form "a is much closer to b than c is to d," for consistency. If the set is consistent, then the algorithm returns a cluster tree that satisfies the constraints. The algorithm builds the cluster tree from top to bottom dealing first with the large distances, and then proceeding to smaller and smaller distances.

Let S be a system of constraints of the form od(a, b) ≪ od(c, d); and let T be a cluster tree. We will say that THS (read "T satisfies S") if every instantiation of T satisfies S. In this section, we develop an algorithm for finding a cluster tree that satisfies a given set of constraints.

The algorithm works along the following lines: Suppose we have a solution satisfying S .

Let D be the diameter of the solution. If S contains a constraint od( a, b ) ≪ od( c, d ) then, since od( c, d ) is certainly no more than D, it follows that od( a, b ) is much smaller than D.

We label ab as a "short" edge.

If two points u and v are connected by a path of short edges, then by the triangle inequality the edge uv is also short (i.e. much shorter than D ). Thus, if we compute the connected components H of all the edges that have been labelled short, then all these edges in H can likewise be labelled short. For example, in table 3, edges vz, wx, and xy can all be labelled "short".

On the other hand, as we shall prove below, if an edge is not in the set H, then there is no reason to believe that it is much shorter than D. We can, in fact, safely posit that it is the same o.m. as D . We label all such edges "long".

We can now assume that any connected component of points connected by short edges is a cluster, and a child of the root of the cluster tree. The root of the cluster tree is then given the largest label. Its children will be given smaller labels. Each "long" edge now