Why does Nearest not return both equally distant values?

Question

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]

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}}}

C. E. · Answer

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] &)]

Michael E2 · Answer

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.

Why does Nearest not return both equally distant values?

2 Answers

Add your own answers!

Ask a Question