# Distance between patterns of points

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.

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

• 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? – Intelligenti pauca Aug 24 '17 at 10:00
• 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 – Euler_Salter Aug 24 '17 at 10:05
• I am sure there are many different approaches, mine was just a matching approach – Euler_Salter Aug 24 '17 at 10:06
• 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. – Intelligenti pauca Aug 24 '17 at 10:22
• I see: I edited your title to avoid an improper use of "similarity". – Intelligenti pauca Aug 24 '17 at 10:44

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).$$

• 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 – Euler_Salter Aug 24 '17 at 11:53
• @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 – Alex Ravsky Aug 24 '17 at 12:42
• At Wiki’s page to the approach is relevant only a section on finitely dimensional $p$-norm. – Alex Ravsky Aug 24 '17 at 12:42