minimum distance between two set of 2D points (x1,y1) , (x2,y2)

Question

I have a problem as described in the title and I am using MATLAB 2020.

I have 2 sets of 2D points, and I want to find the two points (each point from a different set) that has the minimal distance from all the other points min(distance(pi,pj)) I done some research (google) and found this article: "Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets" in this web page:

What is the fastest algorithm to calculate the minimum distance between two sets of points?

I tried to implement the algorithm, using MATLAB, and a code for Garbriel graph (which I found in google) here:

http://matgeom.sourceforge.net/doc/api/matGeom/graphs/gabrielGraph.html

the problem is that when I run the code,which suppose to be the algorithm vs a "brute force algorithm" (two loops) , the brute force is always faster... no matter how many points I used , and it is way faster... which is in contrast to logic (mine) and the article mention above.

when I check the execution time of the code lines, I found that the line

dist = dist + (repmat(p1(:,i), [1 n2])-repmat(p2(:,i)', [n1 1])).^2;

in :

minDistancePoints(p1, varargin)

is the "problem" and advises? thank you

p.s let

set1=random(100,2) 
set2=random(100,2)

i want to find the point1 in set1 and the point2 in set2 that have minimum distance from all the other points.

Can you share an example? Bruteforce will be faster if each of your set of 2D points have 1 point. Likely the alternative will be faster if you have 1 million points. Maybe the implementations of each of the methods are suboptimal. We can't know without a complete example — Ander Biguri
That Gabriel graph routine (1) seems to itself compute all pairs distances (2) calls delaunayn. You should just build on top of delaunayn directly. — David Eisenstat

obchardon obchardon · Accepted Answer · 2020-07-28T09:00:11

Using implicit expansion, we can compute all the possible combination at once and then find point in p1 that minimize the sum of the distance:

p1 =    [0 -1;
         2 3;
         8 8]
p2 =    [1 1;
         2 3;
         3 5;
         3 3]
         
[~,closest_p1] = min(sum(sum((permute(p1,[3,2,1])-p2).^2,2).^0.5))

I add a dimension to p1 with: permute(p1,[3,2,1]), so now we can compute all the combination in this new third dimension.

closest_p1 give the index of the point that minimize the sum of the euclidian distance between each points in p2. In this example closest_p1 = 2.

Noticed also that the algorithm that you use seems to also compute all the possible combination.

minimum distance between two set of 2D points (x1,y1) , (x2,y2)

1 Answers