closest-pair-doubling

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

📝 Project report

:pagewith_curl: [Outputs and data](https://github.com/ThangMinhCao/closest-pair-doubling/tree/master/report/images%26_data)

Prerequisites

Notes

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.

Install

git clone git@github.com:ThangMinhCao/closestpairdoubling.git
cd closestpairdoubling
cmake .
make

Test the program

In the cloned directory of the repo:

./closestpairdoubling

Author

Minh Thang Cao

Github: @ThangMinhCao
LinkedIn: @minhthangcao