1
$\begingroup$

I was thinking of the following problem: Imagine I am given two lists of points on a 2D plane. These lists have the same size, i.e. both lists have the same number of points.

Now, I want to be able to compare these two patterns of points. How could I do that mathematically/statistically?

My try

I calculated the distance (Euclidean) from each point to every other point (pairwise distance). Then, I've ordered these distances. After that, I pick the first pair which will be the distance between two points a and b. At this point, I will ignore any other distance containing a or b (if a is in the first pattern and b in the second pattern). Thus at the end I will have a "matching" that creates a minimum weight match.

Finally, I just sum up these distances and this is my distance coefficient.

Any other ideas?

An example Suppose I have: $[ (0,0), (0,1), (1,0), (1,1)]$ and $[(0,0), (2,1), (0,1), (1,0)]$ and $[(2,3), (2,0), (0,0), (0,2)]$

These are three different patterns of points. I want to assess how similar they are. pattern1

pattern2

pattern3

How similar are they? Which are the most similar pairs? I want to answer questions like these.

$\endgroup$
8
  • $\begingroup$ It is not clear what you want to obtain. Do you want to couple every point in the first list with the point nearest to it in the second list? $\endgroup$ – Intelligenti pauca Aug 24 '17 at 10:00
  • $\begingroup$ This was my approach to the problem, yes. My question is, is there a better approach? If so, which? I am sure this should be a well-studied problem, but I can't seem to find any documentation. I just want to assess the similarity of the two patterns $\endgroup$ – Euler_Salter Aug 24 '17 at 10:05
  • $\begingroup$ I am sure there are many different approaches, mine was just a matching approach $\endgroup$ – Euler_Salter Aug 24 '17 at 10:06
  • $\begingroup$ It is not clear what you mean by "assess the similarity of the two patterns". Similarity has a well defined meaning in geometry, but I don't think it is the one you have in mind. What kind of "similarity" are you looking for then? An example would be probably of help. $\endgroup$ – Intelligenti pauca Aug 24 '17 at 10:22
  • 1
    $\begingroup$ I see: I edited your title to avoid an improper use of "similarity". $\endgroup$ – Intelligenti pauca Aug 24 '17 at 10:44
1
$\begingroup$

The first idea which came to my head was Hausdorff distance.

If you are interested in the similarity not of the placements of the points of the given sets (say $A$ and $B$), but only of their patterns (which are invariant with respect to isometries of the plane), you can use the counterparts of $\ell_p$-metric with $1\le p\le\infty$ (most popular values of $p$ are $1$, $2$, and $\infty$)

$$d(A,B)=\min_\sigma \left(\sum_{a,a’\in A} |d(a,a’)-d(\sigma(a),\sigma(a’))|^p \right)^{1/p},$$

where the minimum is taken with respect to all bijections $\sigma$ between the sets $A$ and $B$. The power $1/p$ is taken with hope to assure the trinagle inequality

$$ d(A,B)\le d(A,C)+ d(C,B).$$

$\endgroup$
3
  • $\begingroup$ Thank you. Do you know if there is any implementation in any programming language? (maybe Python?) Also, is this the corresponding Wikipedia page for $l_p$-metric? en.wikipedia.org/wiki/Lp_space $\endgroup$ – Euler_Salter Aug 24 '17 at 11:53
  • $\begingroup$ @Euler_Salter Unfortunately, I don’t know about program implementations of this straightforward approach, but they should not be long or complicated. The most complex part of it is to write a procedure which generates all bijections, but it is essentially the same as a generation of all permutations of $n$-element set, which should be well-known and easy to find. Also, although from a mathematical point of view the approach is OK, its serious caclulational drawback is its high complexity $O(n!n^2)$, which makes it inapplicable for big $n$.So we need to devise another approaches for these cases $\endgroup$ – Alex Ravsky Aug 24 '17 at 12:42
  • $\begingroup$ At Wiki’s page to the approach is relevant only a section on finitely dimensional $p$-norm. $\endgroup$ – Alex Ravsky Aug 24 '17 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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