Confused with Euclidean distance and radius

Question

I have N points in D dimensions and a query point q in D dimensions. I have to check if the points lie in Euclidean distance less than a given radius r. So I can do:

for every point p:
  check if Euclidean_dist(p, q) < r

However, I must do this in a computer program with c++ and the Euclidean distance requires a square root which is very time-costly for a computer.

Would this be equivalent?

for every point p:
  check if squared_Euclidean_dist(p, q) < r²

Note that 'squared_Euclidean_dist()' won't square root the dot product.

Answer 1

Yes, that would be mathematically equivalent, since:

$$a,b \ge 0 \quad \implies\quad \big( a \lt b \iff a^2 <b^2\big)$$

Computation-wise it may be worth noting that the squared distance will have a different range, and (at the ends of the range) possibly different precision also, compared to the distance itself.

Answer 2

In theory, this is true, but make sure you have your numerical accuracy in place.

E.g. for very small $a$, you could have $a^2 = 0$. Or for very large $a$, you could have overflow on $a^2$.