3
$\begingroup$

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.

  • 0
    Assuming that when you say metric you mean metric, see [Hausdorff distance](http://en.wikipedia.org/wiki/Hausdorff_distance).2012-09-02
  • 0
    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.2012-09-02
  • 0
    That seems to do the job. @Karolis Juodelė can you post it as an answer so I can mark it as correct?2012-09-02

1 Answers 1

2

A metric in a set of compacts is Hausdorff distance.