Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

A metric in a set of compacts is Hausdorff distance.

share|cite|improve this answer

Your Answer


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.