1
$\begingroup$

Let's say, for the sake of the question, I have 3 sets of real numbers of variate length:

$\{7,5,\tfrac{8}{5},\tfrac{1}{9}\},\qquad\{\tfrac{2}{7},4,\tfrac{1}{3}\},\qquad\{1,2,7,\tfrac{4}{10},\tfrac{5}{16},\tfrac{7}{8},\tfrac{9}{11}\}$

Is there a way to calculate the overall distance these sets have from one another? Again, there are only 3 sets for the sake of the example, but in practice there could be $N$ sets as such:

$\{A_1,B_1,C_1,\ldots,N_1\},\qquad \{A_2,B_2,C_2\ldots,N_2\},\;\ldots \quad\{A_n,B_n,C_n,\ldots,N_n\}$

These sets of reals can be considered to be sets in a metric space. The distance needed is the shortest overall distance between these sets, similar to the Hausdorff distance, except rather then finding the longest distance between 2 sets of points, I am trying to find the shortest distance between N sets of points.

  • 0
    Let's start with a simple case to see if we can make any sense of the problem. Suppose your sets have only one point each, and there are just three of them, namely, $X$ contains 1, $Y$ contains 2, and $Z$ contains 17. What would you consider to be "the shortest overall distance between these sets," and why?2011-11-05

1 Answers 1

2

Let $E(r)$ be the set of all points at distance at most $r$ from the set $E$. This is called the closed $r$-neighborhood of $E$. The Hausdorff distance $d_H(E_1,E_2)$ is defined as the infimum of numbers $r$ such that $E_1\subseteq E_2(r)$ and $E_2\subseteq E_1(r)$. There are at least two reasonable ways to generalize $d_H(E_1,E_2)$ to $d_H(E_1,\dots,E_N)$:

  1. $d_H(E_1,\dots,E_N)$ is the infimum of numbers $r$ such that $E_i\subseteq E_j(r)$ for all $i,j\in\{1,\dots,N\}$.
  2. $d_H(E_1,\dots,E_N)$ is the infimum of numbers $r$ such that $E_i\subseteq \bigcup_{j\ne i}E_j(r)$ and $\bigcup_{j\ne i}E_j(r)\subseteq E_i$ for all $i$.

Both 1 and 2 recover the standard $d_H$ when $N=2$. Distance 1 is larger, and is somewhat less interesting because it's simply $\max_{i,j} d_H(E_i,E_j)$. Both distances turn into $0$ if and only if $E_1=\dots = E_N$.