|
|
Closest Pair of Points - Divide and Conquer
|
|
This was an exercise in implementing an O(nlgn) algorithm for finding the closest pair of XY coordinates in a large data set. The implementation includes a simple merge sort for sorting the points by their X and Y coordinates before using a divide and conquer algorithm to find the closest pair. In this case extra checking was involved to ensure a specific result was returned. The algorithm prioritizes the leftmost pair of points, but if multiple exist it will also prioritize the lowest of the leftmost pairs and if still multiple exist the algorithm will prioritize the oldest of the resultant pairs.