Closest Pair of Points $(10$ points$)$: Computing the closest pair of points from a collection

of $n$ points takes $(n^2)$ naively, by checking each point against every other point and keeping

track of the minimum distance seen. We would like to improve upon that solution.

For this problem, you are not provided any helper code. The input will be provided in a

file named points.txt$,$ which contains $1$ million points, each described by an $x$ and $y$ value

on the same line, each in the range $(0,0)$ to $(1000000,1000000).$ The distance can be

computed via

$d=\sqrt[\phantom{2}]{(x_2-x_1{)}^2+(y_2+y_1{)}^2}$

Comparing all pairs of points is infeasible with $1$ million points. Instead, we will divide

the grid into $bb$ grids, each of size $\frac{1000000}{b}\frac{1000000}{b}.$ Each point is then hashed into its

specific grid based on its location, and need only to be compared to points in its grid and in

the neighboring $8$ grids. This reduces the total number of comparisons needed, provided we

choose a good grid size. You can experiment yourself to find the best possible value of $b.$

Each grid cell should contain a linked list of the points that hashed to that location. If you

create a Node class to store the points, the two dimensional grid could be declared by writing:

Your program should follow the following steps:

$($a$)$ Allocate a $2$D array of grid cells, based on your particular choice of $b.$

$($b$)$ Read the input file, hash each point to the corresponding grid cell.

$($c$)$ For each point, compare it against all points in the $3$x$3$ block of grid cells centered on

that point's grid cell. Maintain the smallest distance you've seen.

$($d$)$ Print minimum distance.

Your program should be named Closest. java