Consider the following description of an incorrect algorithm for the closest pair of points in a plane problem. The inpu

[answerhappygod]

Consider The Following Description Of An Incorrect Algorithm For The Closest Pair Of Points In A Plane Problem The Inpu 1 (167.98 KiB) Viewed 49 times

b) Show why this algorithm will not always output the correctanswer. (A drawing of a counterexample with labeled points ordistances and a brief explanation will suffice.)
Consider the following description of an incorrect algorithm for the closest pair of points in a plane problem. The input is n points in the plane; the output is a pair of points with the smallest Euclidean distance between them among all pairs of points. 1. Sort the points according to x-coordinates 2. Sort the points according to the y-coordinates 3. Find a pair of points with minimum difference (in absolute value) be- tween x-coordinates (let da denote this minimum difference) 4. Find a pair of points with minimum difference (in absolute value) be- tween the y-coordinates (let dy denote this minimum difference) 5. If dr ≤dy, output the points found in step 3; otherwise (if d > dy) output the points found in step 4