A Closest pair of points problem solver using the Divide and Conquer Algorithm, Bandung Institute of Technology, made by Kenneth Ezekiel (13521089) and Alisha Listya (13521171) for the Algorithm & Design Course
The closest pair of points problem is, as the name suggests, a problem when: given n number of points, find the closest pair of points by the euclidean distance for the set of points.
This Project aims to take the original problem and solve it on a higher dimension (the original problem was based on 2 Dimensional set of points), with the Divide and Conquer Approach, also comparing it with the Brute Force Approach.
The features of our program:
- Getting the closest pair of points in n-dimensional space
- Divide and Conquer Algorithm + Execution Time + Number of distance calculation operations
- Read and Write to file (I/O)
- Points Visualizer + Write to PNG
- Closest pair of points visualizer
The divide and conquer algorithm for finding the closest pair of points in 2 Dimensional is already known widely, dividing the points into 2 sub-array recusively, and then combining their results, with the consideration of points near the middle point of division (+- delta or the closest distance got from the recursion).
Implementing it into 3 Dimensional space and then n-Dimensional space is a more interesting story as now we also need to consider not a strip from the middle point, but a slab (in 3 Dimensional) and a more complex structure in n-Dimensional space. But our approach to this problem uses the sparsity condition and limits the Time Complexity for O(n^2) into O(n*log n).
│
│ README
│
├─── doc
│ Tucil2_13521089_13521171
├─── input
│ test
├─── src
│ ├─── Modules
│ │ Bruteforce.py
│ │ DivideandConquer.py
│ │ InputHandler.py
│ │ Sorting.py
│ │ Visualizer.py
│ └─── main.py
└─── test
visualizer.png
To run the program, simply run the main.py python script in the src folder
- Numpy
- Matplotlib
- Os
- Time
- Math