Denote the collection of all finite subsets in $\mathbb{R}^d$ as $\mathcal{S} = \{S \subseteq \mathbb{R}^d: |S| < \infty \}$. What are ways to define distance metrics on $\mathcal{S}$ that can be efficiently computed? For instance, one could define $$ d(A, B) = \frac{1}{|A|\cdot|B|} \sum_{x\in A}\sum_{y\in B} \|x - y\|_2^2 $$ but I'm not sure if the triangle inequality is satisfied?
Asked
Active
Viewed 142 times
1
-
Could you be precise about what you mean by a distance metric? – Matt Aug 09 '18 at 21:54
-
@Matt: I mean a metric that satisfies the requirements: https://en.wikipedia.org/wiki/Metric_(mathematics) – p-value Aug 09 '18 at 21:59
-
Could you use the discrete metric? – Matt Aug 09 '18 at 22:02
-
@Matt: What to is your definition of the discrete metric? – p-value Aug 09 '18 at 22:03
-
If $x = y$ then $d(x,y) = 0$. Otherwise, $d(x,y) = 1$. – Matt Aug 09 '18 at 22:04
-
@Matt: Yes, you are correct that that is a valid metric, but I was looking for a more practical option, since if the elements in $A$ and $B$ are in $\mathbb{R}^d$, then $A\neq B$ with probability one. – p-value Aug 09 '18 at 22:08
-
I'm not sure what you mean by a "more practical option". Perhaps you can elaborate on this a little in an edit to your original question? – Matt Aug 09 '18 at 22:10
-
1Is Hausdorff distance what you are looking for? – Adam Francey Aug 09 '18 at 23:59
-
Thanks @AdamFrancey; yes, that would definitely be an option. – p-value Aug 13 '18 at 04:07
-
Concerning the function $d(A,B)$ from your question, $d(A,A)=0$ iff $A$ is a one-point set, so $d$ is not a metric. – Alex Ravsky Nov 30 '18 at 20:39