Implementing an O(n lg n) algorithm to determine the closest pair of points in a provided set of points.
Table of Contents
The objective of this program is to implement an O(n lg n) algorithm to determine the closest pair of points in a provided set of points P inside the two-dimensional plane.
“Closest” refers to the usual euclidean distance.
This problem has applications in, for example, traffic-control systems. A system for controlling air or sea traffic might need to identify the two closest vehicles in order to detect potential collisions.
To solve this, a divide-and-conquer algorithm will be implemented, which uses O(n lg n) time. The program carries out the divide-and-conquer paradigm as follows.
The set of points is divided into two sets, where each of the x-coordinates and y-coordinates are allocated accordingly to where their point was allocated.
After dividing the set of points into two, make two recursive calls to find the closest pair of points in each of the resulting subsets.
The closest pair can now either be a pair found be the previous two recursive calls, or will be a pair where one point lies in one of the two subsets and one point lies in the other.
To get a local copy up and running follow these simple steps.
Things you need to use the software.
- MacOS
- Xcode
Clone this repo.
git clone https://github.com/vmthanh-bi/Closest-pair-of-points.gitSee the open issues for a list of proposed features (and known issues).
Tony Vu - @vmthanh.bi - vmthanh.bi@gmail.com
Project Link: https://github.com/vmthanh-bi/Closest-pair-of-points