7
$\begingroup$

Define the following three vectors:

a = {0., 0., 0.};
b = {-0.5`, 0.4330127018922193`, 0.25`};
c = {-0.5`, 0.`, 0.`};

Note that the distance from a to c is the same as from b to c.

Norm[a - c] == Norm[b - c]

True

Also

DistanceMatrix[{a, b}, {c}]

{{0.5}, {0.5}}

And yet when I call Nearest it returns only one of the two (b).

Nearest[{a, b}, c]

{{-0.5, 0.433013, 0.25}}

Why is that? I have played with WorkingPrecision but that does not help.

Based on a comment below, I have a work-around of the following form:

Nearest[{a, b}, c, DistanceFunction -> (Round[Norm[#1 - #2] 10^6] &)]

{{0., 0., 0.}, {-0.5, 0.433013, 0.25}}

Thanks to all who took the time!

But speaking of taking the time, the modified DistanceFunction causes the function to run at least 10x slower. Here is a function that is almost as fast as the original but behaves as expected.

MyNearest[points_, tests_] := Block[{dm, mins, pos},
  dm = DistanceMatrix[tests, points];
  mins = Min /@ dm;
  pos = MapThread[Position, {dm, mins}];
  points[[#]] & /@ (Flatten /@ pos)
  ]

MyNearest[{a, b}, {c}]

{{{0., 0., 0.}, {-0.5, 0.433013, 0.25}}}
$\endgroup$
4
  • 2
    $\begingroup$ DistanceMatrix[{a, b}, {c}] // FullForm tells you why... C.E. pointed this out in their answer, but they deleted it. Don't know why. $\endgroup$ Commented Sep 13, 2020 at 20:31
  • $\begingroup$ I restored the answer now. I feel like I haven’t been able to get to the bottom of all the ifs and whys, though $\endgroup$
    – C. E.
    Commented Sep 13, 2020 at 22:47
  • $\begingroup$ MyNearest is much slower for me than @C.E.'s custom DistanceFunction. $\endgroup$
    – Michael E2
    Commented Sep 13, 2020 at 23:44
  • $\begingroup$ Here's a one-bit rounding difference for which MyNearest does not work: SeedRandom[15]; aa = a; bb = RotationTransform[Pi/3, RandomReal[{-1, 1}, {2, 3}], c][a]; MyNearest[{aa, bb}, {c}] -- compare with Norm[aa - c] == Norm[bb - c] $\endgroup$
    – Michael E2
    Commented Sep 14, 2020 at 0:59

2 Answers 2

5
$\begingroup$

Here's a way to get all the points that are equivalent to being Equal in distance:

Nearest[{a, b}, c,
 {All,
 (1 + 10^Internal`$EqualTolerance*$MachineEpsilon) *
   EuclideanDistance[First@Nearest[{a, b}, c], c]}]

Calls Nearest twice unfortunately, but it's about as fast as @C.E.'s on the toy example and much faster on 1000 points.

$\endgroup$
3
$\begingroup$

If you copy the numbers returned by DistanceMatrix into new cells, you can see that they are not exactly the same. The first number copies as 0.5 and the other as 0.49999999999999994.

If you take the outputs Norm[a - c] and Norm[b - c] and copy them into new cells then they will be copied as 0.5.

In any case, 0.49999999999999994 == 0.5 returns true. So it doesn't just come down to the fact that the numbers are slightly different, it also matters that different functions use different definitions of equivalent.

This is a possible work-around:

Nearest[{a, b}, c, DistanceFunction -> (Round[Norm[# - #2], 10^-10] &)]
$\endgroup$
1
  • 1
    $\begingroup$ It appears that Nearest does not "compare with tolerance." Be nice if there were such an option. Also, a custom DistanceFunction usually makes Nearest less efficient, not that it matters on the toy example. +1 all the same. $\endgroup$
    – Michael E2
    Commented Sep 13, 2020 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.