CSS 549 – Algorithm Design and Analysis – Program 2

 

Closest Pair of Points

 

1.       Implement the closest pair of points algorithm. For your output, I want the distance between the closest pair of points in every recursive call (including the overall solution) output to the console. (You don’t need to output the locations of the points.) To make sure that we get the same results for every call, you should make sure that, when there is an odd number of items, the left group (smaller x-coordinates) has one more item than the right group (larger x-coordinates). In any subproblem with three or fewer points, you should calculate the distances using brute-force. For full credit, your algorithm must run in O(n log n) time. Your input file will consist of n points, with n specified on the first line, and n additional lines containing the x- and y-coordinates, which will be real numbers (not integers). The file should be hardcoded to the name “program2data.txt”. For example:

 

8

 0.1251 56.3585

19.3304 80.8741

58.5009 47.9873

35.0291 89.5962

82.2840 74.6605

17.4108 85.8943

71.0501 51.3535

30.3995  1.4985

 

Please output your results with four digits of precision. Format your output identically to mine (with no leading or trailing spaces). My output for this trivial data set is (the indices are after sorting by x-coordinate and the distances include all points in between the two indices):

 

D[0,1]: 34.2222

D[2,3]: 80.1437

D[0,3]: 5.3748

D[4,5]: 47.7726

D[6,7]: 25.8731

D[4,7]: 12.9928

D[0,7]: 5.3748

 

More details:

1.       Do not make any assumptions about the values of the coordinates, except that they can be stored in a double variable (not float).

2.       Use the Euclidean distance between two points: sqrt((x1 – x2)2 + (y1 – y2)2)

3.       You may use either Java or C++. You may use Java libraries and C++ STL for data structures or for sorting. Try not to use anything compiler or version dependent.

4.       Do not have any input from the keyboard, command line parameters, or batch files. The code should run from within an IDE (of my choice) without any user interaction. Hardcode the file to read from.

5.       Submit only source code, all of which reside in the same directory when I compile it. ZIP files are acceptable; no other compressed format is acceptable. Do not use stdafx, targetver, etc. – the code set should be only source files that you write.

6.       You may work in pairs, but you are not required to. Pairs must both be present when all work is done.

7.       Turn in your code at the assignment dropbox. Each pair should turn in only one set of code, but mark both members’ names clearly in the code. The partner who did not turn in code should submit a comment indicating who turned in the code they worked on.

8.       Your code should be able to handle at least 10,000 points. I have posted the above data set and another (without the correct solution) with 100 data points. I will test with far more than that.

9.       Do not try to output a nice format in the output. I want you to get the exact same result as my code. There is only one space (following the colon) and all distances have four digits after the decimal point. There are no leading or trailing blank lines.

10.   See the posted grading rubric for details on how I grade.