Consider the following algorithm to compute the two closest points in a set of n points...

Transcribed Image Text:

Consider the following algorithm to compute the two closest points in a set of n points (sqrt is the square root function). ALGORITHM Brute ForceClosestPoints(P) // Input: A list P of n (n 2) points P = (x1,y1), Pn = (xn, yn) ... // Output: Indices index and index2 of the closest pair of points dmin o for 1 ton - 1 do for ji+1 to n do dsqrt ((x x;) + (yi y;)) if d < dmin dmin d index1+i - return index1, index2 index2+j Activate W Go to Settings a) [10 points] Computing the square root may be thought to be as simple as addition and multiplication. However, this is not true as most square roots are irrational numbers that can only be found approximately and the approximations are not trivial. Explain how you can change the algorithm to avoid computing the square roots (thus relying only on addition/multiplication) while still finding the indices of the two closest points. b) [25 points] Compute the running time of your updated algorithm. Consider the following algorithm to compute the two closest points in a set of n points (sqrt is the square root function). ALGORITHM Brute ForceClosestPoints(P) // Input: A list P of n (n 2) points P = (x1,y1), Pn = (xn, yn) ... // Output: Indices index and index2 of the closest pair of points dmin o for 1 ton - 1 do for ji+1 to n do dsqrt ((x x;) + (yi y;)) if d < dmin dmin d index1+i - return index1, index2 index2+j Activate W Go to Settings a) [10 points] Computing the square root may be thought to be as simple as addition and multiplication. However, this is not true as most square roots are irrational numbers that can only be found approximately and the approximations are not trivial. Explain how you can change the algorithm to avoid computing the square roots (thus relying only on addition/multiplication) while still finding the indices of the two closest points. b) [25 points] Compute the running time of your updated algorithm.