A.4 For points a, b ∈ P, od(a, b) = 0 if and only if a = b.

(The function od is positive definite.)
A.5 For points a, b E P, od(a, b) = od(b, a).

(The function od is symmetric.)
A.6 For points a, b, c E P, and order of magnitude d E D,
if od(a, b) ≪ d and od(b, c) ≪ d then od(a, c) ≪ d, (The om-triangle inequality.)
A.7 There are infinitely many different orders of magnitude. A.8 For any point a 1 E P and order of magnitude d E D , there exists an infinite set a2, a3 . . . such that od(ai, ai) = d for all i = j.

The example we have given above of an om-space, non-standard Euclidean space, is wild and woolly and hard to conceptualize. Here are two simpler examples of om-spaces:
I. Let δ be an infinitesimal value. We define a point to be a polynomial in δ with integer coefficients, such as 3 + 5 δ − 8 δ 5 . We define an order-of-magnitude to be a power of δ . We define δ m ≪ δ n if m > n ; for example, δ ⁰ ≪ δ 4 . We define od( a, b ) to be the smallest power of δ in α − b. For example, od(1 + δ 2 − 3δ 3 , 1 − 5δ 2 + 4δ 4 ) = δ 2 ,
I. Let N be an infinite value. We define a point to be a polynomial in N with integer coefficients. We define an order of magnitude to be a power of N . We define N p ≪ N q if p < q ; for example, N 4 ≪ N 6 . We define od( a, b ) to be the largest power of N in a - b. For example, od(1 + N 2 - 3N 3 , 1 - 5N 2 + 4N 4 ) = N 4 .

It can be shown that any om-space either contains a subset isomorphic to (I) or a subset isomorphic to (II). (This is just a special case of the general rule that any infinite total ordering contains either an infinite descending chain or an infinite ascending chain.)
We will use the notation "d f e " as an abbreviation for "d f e or d = e ".

## 4. Cluster Trees

Let P be a finite set of points in an om-space. If the distances between different pairs of points in P are of different orders of magnitude, then the om-space imposes a unique treelike hierarchical structure on P . The points will naturally fall into clusters , each cluster C
being a collection of points all of which are much closer to one another than to any point in P outside C . The collection of all the clusters over P forms a strict tree under the subset relation. Moreover, the structure of this tree and the comparative sizes of different clusters in the tree captures all of the order-of-magnitude relations between any pair of points in P . The tree of clusters is thus a very powerful data structure for reasoning about points in an om-space, and it is, indeed, the central data structure for the algorithms we will develop in this paper. In this section, we give a formal definition of cluster trees and prove some basic results as foundations for our algorithms.

Definition 2: Let P be a finite set of points in an om-space. A non-empty subset C ⊂ P is called a cluster of P if for every x,y E C, z E P - C, od(x,y) ≪ od(x, z). If C is a cluster, the diameter of C , denoted "odiam( C )", is the maximum value of od( x, y ) for x, y ∈ C .