QUESTION

Text
Image

# Closest-Pair of Points Problem The closest pair of points problem or closest pair problem is to find the two points in a set of $\mathrm{n}$ points (in the two-dimensional Cartesian plane) with the smallest distance between them. This problem arises in several applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision. (A) Write a Brute Force Algorithm to find the two closest points in a set of $\mathrm{n}$ points. Brute-force algorithm computes the distance between every pair of distinct points and return the indexes of the points for which the distance is minimum. Distance between two points $P_{i}\left(x_{i}, y_{i}\right)$ and $P_{j}\left(x_{j}, y_{j}\right)$ : $d\left(P_{i}, P_{j}\right)=\sqrt{ }\left[\left(x_{i}-x_{j}\right)^{2}+\left(y_{i}-y_{j}\right)^{2}\right]$ Analyze your algorithm to find time efficiency (Q). (B) Using divide and conquer strategy, we can do it faster. Main idea is as follows: Sort the input array according to $x$ coordinates. Find the middle point in the sorted array. Divide the given array in two halves. Recursively find the smallest distances in both subarrays. From the above steps, we have an upper bound $d$ of minimum distance. Now we need to consider the pairs such that one point in pair is from the left half and the other is from the right half. Write the complete algorithm based on the above idea and analyze your algorithm to find time efficiency $(\mathrm{Q})$. (C) Write a program in Java based on both of your algorithms, one method based on Brute Force and the second method based on Divide and Conquer. For the purpose of testing, generate 1000 points in the main using class Random and save these points in an array. Assume that $\mathrm{x}$-coordinate ranges from 1 to 5000 and y-coordinate also ranges from 1 to 5000 . Call both methods from main, output minimum distance points and find its actual execution time using built-in time methods of Java  