<p>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. </p>

<p>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$)</p>

CC BY-SA 2.5
2011-01-19T21:48:56.110Z
Good point. In fact, I am satisfied with normalizing the space so that $d(x,y) \leq 1$ for all $x, y \in N$. I will add this to the question so that it has a finite answer.
Aaron Roth
CC BY-SA 2.5
2011-01-19T21:16:54.940Z
2011-01-19T21:16:54.940Z
Suresh Venkat
<p>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).</p>

<p>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.</p>

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

CC BY-SA 2.5
2011-01-20T15:23:03.367Z
Thanks! I see that my question reduces to asking for bounds on the volume of the n^2 dimensional metric polytope, which seems like it might be a hard problem...
Aaron Roth
CC BY-SA 2.5
2011-01-19T22:38:19.370Z
2011-01-19T22:38:19.370Z
Yoshio Okamoto
<p>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$.</p>

<p>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|$$</p>

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

<p>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&#39; \in S$ such that $\partial(d, d&#39;) \leq \epsilon$.)</p>

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

<p>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) &lt; n^2$.  </p>

CC BY-SA 2.5
2011-01-20T18:19:54.980Z
I have asked on mathoverflow whether asymptotic bounds are known on the volume of the metric polytope. http://mathoverflow.net/questions/52661/estimating-the-volume-of-the-metric-polytope
Aaron Roth
<co.combinatorics><metrics><epsilon-nets>
Counting Metrics
Aaron Roth
# Counting Metrics

(Asked by: username_0 on 2011-01-19)

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$.

**Tags:** co.combinatorics, metrics, epsilon-nets
> **Comments:**
> **username_0**: I have asked on mathoverflow whether asymptotic bounds are known on the volume of the metric polytope. http://mathoverflow.net/questions/52661/estimating-the-volume-of-the-metric-polytope  

---

## 2 answers

### Answer by username_2 on 2011-01-19. Score: 7 | Accepted answer

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>

> **Comments:**
> **username_0**: Thanks! I see that my question reduces to asking for bounds on the volume of the n^2 dimensional metric polytope, which seems like it might be a hard problem...  

---

### Answer by username_1 on 2011-01-19. Score: 4

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$)

> **Comments:**
> **username_0**: Good point. In fact, I am satisfied with normalizing the space so that $d(x,y) \leq 1$ for all $x, y \in N$. I will add this to the question so that it has a finite answer.  

---

