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 in this part 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, we do not care about the worst case (theoretical) running time of your method.
Admittedly, "significantly faster" is not very specific, but at a minimum, it means that as the size of the input increases, your algorithm should be faster than the quadratic one, and furthermore, the ratio of the time for your algorithm to the time for the quadratic algorithm should get noticeably smaller.
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.
Here you should speculate/experiment on how the time taken by your algorithm would be impacted if the input, instead of being randomly generated, were to be chosen by an adversary. For example, your observation could be of the form "I don't expect the time taken to be affected significantly, and this is why." Or "Here is an input on which my algorithm does significantly worse than on randomly generated inputs." You can add these observations to the above text file.
If you do want to implement the quadtree based algorithm (which you don't have to), and you're wondering when I'll post the notes, they're finally here.. If you want to do the assignment in a language other than Java, that's quite alright.