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

📃 Outputs and data

Prerequisites

• cmake >= 3.16
• boost >= 1.69.0

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

License

Copyright © 2020 Minh Thang Cao.
This project is MIT licensed.