Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Do you have a definition of the "distance" you want to calculate, or is it part of the task to find a reasonable meaning of the word in this context? If the former, please edit the question to contain the definition. If the latter, edit the question to say something about what you will be using the distance for, and which properties you need it to have. –  Henning Makholm Nov 5 '11 at 4:53
    
I've edited the question to include more information. –  Tom King Nov 5 '11 at 5:00
    
That's still rather unclear. Do you mean the minimum distance of any pair of points from two different sets? –  joriki Nov 5 '11 at 6:21
    
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? –  Gerry Myerson Nov 5 '11 at 8:27

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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