2
$\begingroup$

Suppose I have some 3D points, e.g. {{0, 0, 1}, {0, 0, 1.3}, {0, 1, 0}, {1.2, 0, 0}}. Now I want to find the smallest and largest distance between two points.

A trivial way is to find all possible distances, then look for the smallest and largest number.This becomes very much time-consuming for large data sets.

Could you please suggest any alternative?

$\endgroup$
  • 2
    $\begingroup$ The smallest distance can be found with Nearest. For small point sets DistanceMatrix computes all distances in one go. $\endgroup$ – Henrik Schumacher Mar 5 at 10:21
  • 2
    $\begingroup$ The complexity of finding the largest distance can be reduced with ConvexHullMesh since the maximal distance must be realized by points on the boundary of the convex hull. Depending on the distribution of points, this may have a tremendous effect (or not). $\endgroup$ – Henrik Schumacher Mar 5 at 10:26
  • 3
    $\begingroup$ I am a bit occupied at the moment. Please read the "Details and Options" section in the documentation of Nearest. (It is always a good idea to read the documentation of a new built-in symbol first.) $\endgroup$ – Henrik Schumacher Mar 5 at 10:51
  • 3
    $\begingroup$ @DanielLichtblau Nope. Think of an equilateral triangle: The circumradius is larger than the edge lengths of the triangle, but the latter are the maximal distances. $\endgroup$ – Henrik Schumacher Mar 7 at 16:05
  • 2
    $\begingroup$ This is probably relevent: citeseerx.ist.psu.edu/viewdoc/… $\endgroup$ – Henrik Schumacher Mar 7 at 18:10
7
$\begingroup$

I think Henrik meant the following approach using Nearest:

min[pts_] := Min @ Nearest[pts->"Distance", pts, 2][[All, 2]]

Let's compare the above approach with a simple version based on DistanceMatrix:

min2[pts_] := With[{dm = DistanceMatrix[pts]},
    Min[dm + Max[dm] IdentityMatrix[Length[pts], SparseArray]]
]

Sample data:

SeedRandom[1]
pts = RandomReal[10,{1000,2}];

Timing comparison:

min[pts] //RepeatedTiming
min2[pts] //RepeatedTiming

{0.000693, 0.009433}

{0.00629, 0.009433}

A similar treatment is possible for the maximum distance, but is much slower:

max[pts_] := Max @ Nearest[pts->"Distance", pts, All][[All, -1]]
max2[pts_] := Max @ DistanceMatrix[pts]

Comparison:

max[pts] //RepeatedTiming
max2[pts] //RepeatedTiming

{0.019, 13.7336}

{0.00296, 13.7336}

Note that methods to compute the maximum distance based on ConvexHullMesh will be slower than using DistanceMatrix, e.g.:

ConvexHullMesh[pts]; //AbsoluteTiming

{0.012535, Null}

which is already 4 times slower, without computing any distances yet. Also, methods computing a bounding ball will not yield the correct result. For example, consider an equilateral triangle in 2 dimensions:

With[{eq = SSSTriangle[1, 1, 1]},
    Graphics[{eq, Circumsphere @@ eq}]
]

enter image description here

Clearly the diameter of the circle is larger than the maximum distance.

$\endgroup$
  • $\begingroup$ Thanks Carl, this is exactly what I meant. $\endgroup$ – Henrik Schumacher Mar 7 at 17:43
1
$\begingroup$

You can find out all the distances by calculating the DistanceMatrix. Using Min and Max you can find the smallest and largest values.

dm = {{0, 0, 1}, {0, 0, 1.3}, {0, 1, 0}, {1.2, 0, 0}} // DistanceMatrix
closest = Min@dm (* is 0 since the point is infinitly close to itself. *)
furthest = Max@dm 
closest2 = # /. 0. -> Infinity & /@ dm // Min
$\endgroup$
  • $\begingroup$ From the OP: "A trivial way is to find all possible distances, then look for the smallest and largest number." which is what you suggested. I think the OP wanted something faster that could work for large point clouds. $\endgroup$ – MarcoB Mar 7 at 14:56
  • $\begingroup$ @MarcoB Thanks, didn't read that. $\endgroup$ – Gladaed Mar 7 at 15:02
  • 1
    $\begingroup$ Well, for the max distance you don't have to; you can rely on algorithms that calculate the convex hull and then measure that; alternatively, as Daniel Lichtblau suggested in comments, you can calculate the minimal enclosing sphere (which happens to also be implemented in the BoundingRegion function. The point of the OP was to see if there is an algorithm to avoid the calculation of all distances. $\endgroup$ – MarcoB Mar 7 at 15:06

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.