lrose07 / closestpairanalysis

Closest Pair Analysis

Project for Radford University ITEC 360

This program computes the closest pair of points from a list of x, y coordinate points, using both the brute force and divide and conquer algorithms.

To compile: javac *.java

To run: java Driver <flag> < <filename>

Where flag can be:

• brute: runs the brute force algorithm
• divide: runs the divide and conquer algorithm
• both: runs both

And filename is a file containing a list of points, where the first line of the file is the number of points that follow, one pair of coordinates per line.

Dev Mode:

To enter dev mode, run java Driver -dev

The program will ask how many points (created randomly) and how many runs to perform. It will run both brute and divide.

closestpairanalysis's Issues

Broken for certain data set

Div/Con alg does not give correct result for the following data set:

8
100 1
200 2
300 3
400 4
401 8
500 7
600 6
700 5

Expected: brute force and div/con solution should have the same closest pair and smallest distance. Brute force is always correct (fully tested). Something is broken with div/con for this particular data set, and I assume ones like it. Not sure what about this data set is causing the issue; further investigation needed.

Actual output:

*******************
Brute Force Solver

Time to read/parse array: 1 milliseconds
Time to compute 8 points: 0 milliseconds
Closest pair: (x: 400, y: 4) and (x: 401, y: 8)
with a distance of 4.123105625617661
Algorithm made 30 distance calculations.

*******************
Divide and Conquer Solver

Time to parse/sort: 1 milliseconds
Time to compute 8 points: 0 milliseconds
Closest pair: (x: 401, y: 8) and (x: 500, y: 7)
with a distance of 99.00505037623081
Algorithm made 8 distance calculations.
Algorithm made 7 recursive calls.