# Distance of two sets and their closest points

Assume we have a metric space $S$, a metric $d$ and two subsets of it, called $A$ and $B$. Assume also that $A\cap B = \emptyset$. Assume also that at least one of these sets is bounded, ie. has no sequence of points where the the distance between points gets infinitely large.

Then we define the distance between $A$ and $B$ as $\min \{ d(a,b)| a \in \bar A, b \in \bar B\}$, the points a and b belong to the closure of the respective set.

When $S = \Re^n$ (vectors of real numbers), it is clear (if someone can explain why, would be great) that $d(A,B) = d(\partial A, \partial B)$, ie, the two points $a \in A, b \in B$ that are closest to each other and belong to different sets, are also members of the respective boundary of the set they belong to.

I would like thoughts on when this is true in general. When the is the distance between two sets the same as the distance of their boundaries?

-
It is pretty clear intuitively for $\mathbb{R}^n$: for any $a \in \bar A \setminus \delta A$, $b \in \bar B \setminus \delta B$ you can look at the line passing through $a$ and $b$ and take the intersections $a', b'$ with $\delta A$ and $\delta B$, respectively; then $a'$ and $b'$ will be closer to each other than $a$ and $b$. – Adeel Nov 18 '12 at 0:15
@Adeel : Yes, it is geometric intuition for reals, thats why I said clear :) Thanks for comment. I am interested if this is result can be generalised at all and if, how. – Valtteri Nov 18 '12 at 0:22
In general, the minimum doesn't even have to exist. Recall that every metrizable space can be metrized by a bounded metric. – Michael Greinecker Nov 18 '12 at 0:33
I take it that a bounded metric means that d is limited upwards. One case where my claim fails is the trivial metric for reals, as then EVERY pair of points from A and B is closest, their distance being one. So, I am really asking IF such closest points can be found, then they are at the boundary. Also, in the trivial case, I wonder if the concept of boudary is even meaningful... – Valtteri Nov 18 '12 at 0:36
And as @Michael said, every metric space has an equivalent bounded metric. – Brian M. Scott Nov 18 '12 at 0:38

Your definition of distance between sets $A$ and $B$ doesn't work for some metric spaces. Consider two examples.

Let $S = \mathbb{Q}$. Let $A=[0,\sqrt{2}) \cap \mathbb{Q}$ and $B = \{2\}$. Sets $A$ and $B$ are closed bounded subsets of the metric space $S$. However, $\min\{d(a,b): a\in A, b\in B\}$ is not defined (but $\inf\{d(a,b): a\in A, b\in B\} = 2 - \sqrt{2}$).

Now let $S = \ell_1$. Let $e_i$ be the standard basis of $\ell_1$. Let $A = \{e_i: i\in{\mathbb{N}}\}$ and $B = \{(1 - 1/i) e_i: i\in{\mathbb{N}}\}$. Sets $A$ and $B$ are bounded and closed. Again, $\min\{d(a,b): a\in A, b\in B\}$ is not defined (but $\inf\{d(a,b): a\in A, b\in B\} = 0$).

To avoid this problem, let us assume that $A$ and $B$ are compact sets (or, alternatively, that $S$ is a complete metric space, and $A$ and $B$ are totally bounded sets).

To ensure that $d(A,B) = d(\partial A, \partial B)$, it is sufficient to assume that $S$ is a path metric space (of course, it is a sufficient but not a necessary condition). Recall that $S$ is a path metric space if the distance between every pair of points equals the infimum over of the lengths of curves joining the points (see [Gromov “Metric structures for Riemannian and non-Riemannian spaces”]). In particular, all normed spaces are path metric spaces. Also a closed Riemannian manifold equipped with the geodesic metric is a path metric space.

Proof. Suppose that $S$ is a path metric space. Consider compact subsets $A,B \subset S$. We want to prove that $d(A,B) = d(\partial A, \partial B)$. Suppose to the contrary that $d(A,B) < d(\partial A, \partial B)$. Let $a\in A$ and $b\in B$ be such that $d(a,b) = d(A,B)$.

Choose $\varepsilon > 0$ such that $(1 + \varepsilon) d(A,B) < d(\partial A, \partial B)$. Since $S$ is a path metric space, there is a curve $\gamma:[0,1]\to S$ with $\gamma(0) = a$ and $\gamma (1) = b$ of length at most $(1 + \varepsilon) d(A,B)$. This curve cannot intersect both $\partial A$ and $\partial B$, as otherwise the distance between $\partial A$ and $\partial B$ would be at most $(1 + \varepsilon) d(A,B)$. On the other hand, $\gamma(t_A) \in \partial A$ for $t_A = \sup \{t: \gamma(t) \in A\}$ and $\gamma(t_B) \in \partial B$ for $t_B = \inf \{t: \gamma(t) \in B\}$. We get a contradiction. QED

Here is an example when $d(A,B) \neq d(\partial A, \partial B)$. Let $S= [-1,1]\times \{0,1\}$. Define \begin{align*} d((x,0),(y,0)) &= d((x,1),(y,1)) = |x-y|;\\ d((x,0),(y,1)) &= |x| + |y| + 1. \end{align*} It is easy to verify that $(S, d)$ is a complete metric space. Let $A = [-1,1] \times \{0\}$ and $B = [-1,1] \times \{1\}$. We have, $\partial A = \{-1,1\} \times \{0\}$ and $\partial B = \{-1,1\} \times \{1\}$. Thus $$d(A,B) = d((0,0), (0,1)) = 1$$ but $$d(\partial A, \partial B) = d((1,0),(1,1)) = 3.$$

-
Very thorough and good answer, thank you very much. I admit that my choises of definition of metric was not good one, should have probably used infimum, I was thinking very much from the POW of real space, hence closed sets..Iin your second example, does l denote sequence space? – Valtteri Nov 18 '12 at 10:27
Yes, $\ell_1$ is the set of infinite sequences with the metric $d(x,y) = \sum_{i=1}^{\infty} |x_i - y_i|$. Basis vector $e_i=(0,\dots,0,1,0,\dots)$ is defined by $(e_i)_i = 1$, $(e_i)_j = 0$ for $j\neq i$. – Yury Nov 18 '12 at 13:11

Well, let's try comparing the two distances $d(A,B)$ and $d(\partial A, \partial B)$. Clearly, since boundary of any set is contained in that sets closure, $d(\partial A, \partial B)\geq d(A,B)$.

To answer your question, let's see if/when we can establish the opposite inequality. First of all, to make things easier, we might as well assume both $A$ and $B$ are closed. Now, pick your favorite pair of points $a\in A$ and $b\in B$. If $a\notin \partial A$, then there is by definition some radius $r>0$ such that $B(a,r)-A=\emptyset$, i.e. such that $B(a,r)\subseteq A$.

What we'd like to do is to find a point $a'$ in $B(a,r)$ which is closer to $b$ than $a$ is. In the case of Euclidean space, or any normed vector space, this is easy---simply draw a straight line segment from $a$ to $b$, and take $a'$ to be the intersection of that line segment with $\partial B(a,r)$ (note that since $A$ is closed and $B(a,r)$ is contained in $A$, the closure, and hence the boundary, of $B(a,r)$ is also contained in $A$). I'll have to think about this for a general metric space---my instinct is that it's not the case, but as I'm only beginning my mathematical career, my instinct has often proven wrong!

-
That's very good answer, thanks :) if you come up with more comments, please tell. – Valtteri Nov 18 '12 at 0:54