The closest couple

there are only 1999 points giving just under 2 million pairs to test which can be accomplished in short order on most computers so I didn't bother with any optimizations and simply bashed through all possible pairs to find the closest two.

I'm not going to post my exact (and sloppy) code, but here's the logic I used to solve the problem:

First, know that the same result can be obtained by just bashing through all possible combinations by simply using the distance formula

$distance = \sqrt{(x_{2}-x_{1})^{2} + (y_{2}-y_{1})^{2}}$

with every single combination of points.

However, this would be impractical for problems with more points than just 1999, or even on a slow enough computer, so I broke it up so the computer would not need to test every single possibility. Instead, I first make an 2 dimensional array containing all the points, then I sort it with respect to the first value of each coordinate. Using this, I could establish a running minimum distance, and limit which pairs were even tested based on whether the points' first values were below that.

Say I take the first two points (A and B), and they are 10 units apart (euclidean distance). Since the list is sorted with respect to the first value of the coordinate, once my points are more than 10 units apart between the first value of the coordinate (one dimensional), then I know all the other possibilities (A and F for example) are also going to be more than the minimum distance apart (euclidean distance).

Continuing like this, I also checked if the second value of the coordinate was within range, to save applying the distance formula to it. If it was, then and only then, would the program check the two points, and if closer together than the current minimum, set the new distance as the running minimum.

I should add that to save even more time, since the square root function in the distance formula is so slow, I just kept the "minimum distance" variable squared and then checked the sign of

$distance^{2} - (x_{2}-x_{1})^{2} + (y_{2}-y_{1})^{2}$

and then just took the final minimum distance and took the square root of it, which was $\boxed{290.66303514551004}$

Let ps = { {a,b}, {c,d}, ... }

Then the cartesian product $ps \times ps$ will be all the pairs of the points. Now we can map a distance function over the list.

1

dist[pp_] := Sqrt[ (pp[[1]][[1]]-pp[[2]][[1]])^2 + (pp[[1]][[2]]-pp[[2]][[2]])^2  ]

Finally we remove the zeros and search for the smallest element.

1
2
3
4
5
6
7

1. CartesianProduct[ pts, pts ]
2. Map[ dist,CartesianProduct[ pts, pts ]]
3. Select[ Map[ dist,CartesianProduct[ pts, pts ]],#!=0&]
4. Min[Select[ Map[ dist,CartesianProduct[ pts, pts ]],#!=0&]  ]


Min[Select[ Map[ dist,CartesianProduct[ pts, pts ]],#!=0&]  ]