Function Repository Resource:

ClosestPairOfPoints

Source Notebook

Find the pair of points with the closest distance

Contributed by: Sander Huisman

ResourceFunction["ClosestPairOfPoints"][{p1,p2,p3,}]

finds the pair of points from pi that are closest to each other.

ResourceFunction["ClosestPairOfPoints"][{p1,p2,p3,},"Association"]

returns an Association with the indices of the points, the points and the distance.

Details

The points pi can be in any dimension.
The EuclideanDistance is used to calculate the distances between points.

Examples

Basic Examples (2) 

Given four input points, find the closest in 2D:

In[1]:=
pts = {{0, 0}, {-0.5, 0}, {0.2, 0.1}, {0.5, 0.3}, {0, 0.3}};
cpop = ResourceFunction["ClosestPairOfPoints"][pts]
Out[2]=

Visualize the closest pair:

In[3]:=
Graphics[{Point[pts], Red, Line[cpop]}]
Out[3]=

Scope (4) 

The function can also handle many points:

In[4]:=
pts = RandomReal[{0, 1}, {10000, 2}];
cpop = ResourceFunction["ClosestPairOfPoints"][pts]
Out[5]=

Visualize the closest pair:

In[6]:=
Graphics[{Point[pts], Red, PointSize[Large], Point[cpop], Line[cpop]}]
Out[6]=

Get the indices, the points, and the distance:

In[7]:=
pts = RandomReal[{0, 1}, {100, 3}];
ResourceFunction["ClosestPairOfPoints"][pts, "Association"]
Out[8]=

Find the closest points in 3D:

In[9]:=
pts = RandomReal[{0, 1}, {100, 3}];
cpop = ResourceFunction["ClosestPairOfPoints"][pts];
Graphics3D[{Point[pts], Red, Point[cpop], Line[cpop]}]
Out[10]=

The function can also handle high-dimensional points:

In[11]:=
pts = RandomReal[{0, 1}, {500, 25}];
cpop = ResourceFunction["ClosestPairOfPoints"][pts]
Out[12]=

Properties and Relations (2) 

The function can be naively implemented by checking all pairs:

In[13]:=
pts = RandomReal[{0, 1}, {2000, 2}];
naive = MinimalBy[Subsets[pts, {2}], Apply[EuclideanDistance]][[1]];
faster = ResourceFunction["ClosestPairOfPoints"][pts];
Sort[naive] == Sort[faster]
Out[14]=

The difference is in the speed:

In[15]:=
First /@ {AbsoluteTiming[
   MinimalBy[Subsets[pts, {2}], Apply[EuclideanDistance]];], AbsoluteTiming[ResourceFunction["ClosestPairOfPoints"][pts];]}
Out[15]=

Visualize the difference in speed:

In[16]:=
timing = Table[
   pts = RandomReal[{0, 1}, {n, 2}];
   t1 = First@
     AbsoluteTiming[
      MinimalBy[Subsets[pts, {2}], Apply[EuclideanDistance]][[1]];];
   t2 = First@
     AbsoluteTiming[ResourceFunction["ClosestPairOfPoints"][pts];];
   {{n, t1}, {n, t2}}
   ,
   {n, DeleteDuplicates[Round[2^Range[1, 12, 1/2]]]}
   ];
ListLogLogPlot[Transpose@timing, PlotLegends -> SwatchLegend[{"Naive", "ClosestPairOfPoints"}], Frame -> True, PlotRange -> All]
Out[17]=

The dimension can exceed the number of points:

In[18]:=
pts = RandomReal[{0, 1}, {40, 1000}];
Shallow@ResourceFunction["ClosestPairOfPoints"][pts]
Out[19]=

Possible Issues (3) 

When no points are given a Failure object is returned:

In[20]:=
ResourceFunction["ClosestPairOfPoints"][{}]
Out[20]=

Also a single point is not enough:

In[21]:=
ResourceFunction["ClosestPairOfPoints"][{{1, 2}}]
Out[21]=

For 1D, the coordinate should be between braces:

In[22]:=
ResourceFunction["ClosestPairOfPoints"][{1, 2, 5, 5.5, 8, 9.5}]
Out[22]=

Like this:

In[23]:=
ResourceFunction[
 "ClosestPairOfPoints"][{{1}, {2}, {5}, {5.5}, {8}, {9.5}}]
Out[23]=

Neat Examples (1) 

Check the method against a naive implementation:

In[24]:=
And @@ Table[
  pts = RandomReal[{0, 1}, {Round[10^RandomReal[{1, 2.5}]], RandomInteger[{1, 20}]}];
  a = MinimalBy[Subsets[pts, {2}], Apply[EuclideanDistance]][[1]];
  b = ResourceFunction["ClosestPairOfPoints"][pts];
  a == b
  ,
  {100}
  ]
Out[24]=

Publisher

SHuisman

Requirements

Wolfram Language 14.0 (January 2024) or above

Version History

  • 1.0.0 – 14 April 2025

Related Resources

License Information