Counting Metrics

Question

Say that I have a set of $n$ points $N$, and am interested in metrics $d:N\times N \rightarrow \mathbb{R}$ over $N$. Let $M$ denote the set of all metrics over $N$.

Now let me define the distance between two metrics $d_1$ and $d_2$ in $M$ to be: $$\partial(d_1, d_2) = \left|\sum_{i,j \in N}d_1(i,j)-d_2(i,j)\right|$$

It isn't hard to see that $(M, \partial)$ itself forms a metric space.

I am interested in the size of the smallest $\epsilon$-net of $(M, \partial)$. (i.e. the smallest subset $S \subset M$ such that for all $d \in M$ there is some $d' \in S$ such that $\partial(d, d') \leq \epsilon$.)

Are bounds on this quantity known, and/or are there standard techniques for estimating quantities like this?

EDIT: As Suresh points out, there is no finite $\epsilon$-net if we are talking about unbounded metrics. Let us consider normalized metrics $M$ such that for all $d \in M$, and for all $i,j \in N$, $d(i,j) \leq 1$. Of course now for all $d_1,d_2 \in M$, $\partial(d_1,d_2) < n^2$.

Answer 1

A standard technique is a volume argument. For example, you can look at Chapter 13 of Lectures on Discrete Geometry by Jiri Matousek (Springer, 2002). Then, you need to know (a bound for) the volume of your polytope (the set of all metrics under consideration).

If you restrict your cone by the inequalities $d(x,y)+d(y,z)+d(z,x) \leq 2$ for all $x,y,z\in N$, then the space becomes bounded, which is often called a "metric polytope" or "metric polyhedron" in the literature. The following paper gives the volumes when $|N|\leq 6$, but I couldn't find any study for asymptotics.

A. Deza, M. Deza, K. Fukuda, "On skeletons, diameters and volumes of metric polyhedra", Lecture Notes in Computer Science 1120 (1996) 112–128. http://dx.doi.org/10.1007/3-540-61576-8_78

Answer 2

For the question as stated, you're going to have problems because the space of all metrics is an unbounded cone. In particular, suppose such a bounded $\epsilon$-net did exist and had elements $d_1, \ldots, d_r$. I can always take some metric that lies within one of the $\epsilon$-balls defined by this net, and scale its values so it pops out of all balls.

So you need either some constraint on the metrics themselves, or a different way of defining the set $S$ (maybe $S$ is not a finite set but some set defined by other constraints on $M$)