7
$\begingroup$

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

$\endgroup$
1

2 Answers 2

7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – Aaron Roth
    Jan 20, 2011 at 15:23
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Aaron Roth
    Jan 19, 2011 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.