This homework is about writing a method that takes as input an array of points and finds, for each point in the array, the closest point to it other than itself. The goal is to write this method so that it improves significantly on the time taken by the straightforward algorithm on typical, large, inputs. For the purpose of this assignment, `typical inputs' means the array inputpoints generated here. The program that I have developed so far takes as input the number of points, generates an array called inputpoints with that number of points, runs the straightforward quadratic algorithm on inputpoints, and then prints the time taken by the quadratic algorithm. Having added your method for solving the problem, you should call it on the array inputpoints and then print the time taken by the method.

The method you write should identify the closest points correctly for *all* inputs, and the goal is to design it so that it runs significantly faster than the quadratic one that I have implemented, for large, *typical*, inputs. The comparison of the two methods should be made via the actual times that are calculated. For this assignment, we do not care about the worst case (theoretical) running time of your method.

You have to submit the file containing the program source to a dropbox called Homework3 that I will create on icon. In addition, you should also submit a text file tabulating the time taken by the two algorithms on inputs of size 500, 1000, 5000, 10000, 50000, 100000. For each of the above sizes run the program at least 5 times and report the time taken that in your judgement is typical. This text file should also include an explanation of the ideas you use in your method.