CODEWITHSUNDEEP
algorithmbrute-force
Jessica O'Brien
Jessica O'Brien

Reputation: 155

Closest Pair Brute Force Algorithm - Basic Operation

Given the following pseudo code for calculating the distance between two closest points in the place by brute force:

for (i <-- 1 to n-1) do
    for (j <-- i+1 to n) do
        d <-- min(d, sqrt(xi-xj)^2 + (yi-yj)^2)
return d

The basic operation is computing the square root. But apparently computing square roots in the loop can be avoided by ignoring the square root function and comparing the values (xi-xj)^2 + (yi-yj)^2) themselves. I looked it up and got this "the smaller a number of which we take the root, the smaller its square root, meaning the square root function is strictly increasing". Therefore the basic operation becomes squaring the numbers. Is anyone able to explain this definition?

Upvotes: 0

Views: 1602

Answers (1)

Tim Biegeleisen
Tim Biegeleisen

Reputation: 522007

The easiest way to answer your question is by seeing why you can avoid taking the square root. Consider the following set of distances between points, in ascending order:

{2, 5, 10, 15, 30, ...} = {d1,1, d1,2, d1,3, d2,1, d2,2, ...}

Each one of these distances was computed as the square root of the sum of the x and y distances squared. But we can square each item in this set and arrive at the same order:

{4, 25, 100, 225, 900} = {d1,12, d1,22, d1,32, d2,12, d2,22, ...}

Notice carefully that the positions of the distances, including the minimum distance (the first entry), did not change position.

It should be noted that your pseudo-code does not actually compute the minimum distance, but it could easily be modified to compute this.

Upvotes: 2

Related Questions