Theoretical Computer Science
co.combinatorics metrics epsilon-nets
Updated Mon, 30 May 2022 09:44:21 GMT

Counting Metrics


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




Solution

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) 112128. http://dx.doi.org/10.1007/3-540-61576-8_78





Comments (1)

  • +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... — Jan 20, 2011 at 15:23  


External Links

External links referenced by this document: