# Distance Between Two Sets of Points

Consider two sets of $N$ $n$-dimensiononal points each:

$$\mathcal{X}= \lbrace \mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N \rbrace,$$

$$\mathcal{Y}= \lbrace \mathbf{y}_1,\mathbf{y}_2,\dots,\mathbf{y}_N \rbrace,$$

where $\mathbf{x}_i,\mathbf{y}_i\in\mathbb{R}^n$.

Is there a metric $d(\mathcal{X},\mathcal{Y})$ that defines the 'distance' between these two sets of points, assuming that the ordering of the points in the two sets is not necessarily identical? The metric should ideally be $0$ if there is an exact one-to-one correspondence between the points in the two sets, and increase monotonically as the difference (in some sense) between the two sets of points increases.

-
Assuming that when you say metric you mean metric, see Hausdorff distance. –  Karolis Juodelė Sep 2 '12 at 18:15
Yes, Hausdorff distance is ok as the sets are compact. The calculation iin this specific case is: For each $x_i$ find the minimal distance to any of the $y_j$. And for each $y_i$ find the minimal distance to any of the $x_j$. The Hausdorff distance is the maximum of these $N^2$ numbers. –  Hagen von Eitzen Sep 2 '12 at 18:20
That seems to do the job. @Karolis Juodelė can you post it as an answer so I can mark it as correct? –  Melvin Gauci Sep 2 '12 at 18:25