The implementation in C++ of the closest-pair doubling algorithm which finds the smallest distance between pairs of points in any multi-dimensional metric space in O(n log n) time without directly using the points' coordinates.
Thanks to the work of Anil Maheshwari, Wolfgang Mulzer and Michiel Smid. A Simple Randomized O(N log N)–Time Closest-Pair Algorithm in Doubling Metrics. https://arxiv.org/abs/2004.05883
Because of very large base cases of the algorithm on Euclidean spaces with dimension more than 3D (>= 3 000 000 points) which causes extremely long running time, my test examples and the program only deals with 2D Euclidean spaces.
git clone [email protected]:ThangMinhCao/closestpairdoubling.git
cd closestpairdoubling
cmake .
makeIn the cloned directory of the repo:
./closestpairdoublingMinh Thang Cao
- Github: @ThangMinhCao
- LinkedIn: @minhthangcao
Copyright © 2020 Minh Thang Cao.
This project is MIT licensed.
