Skip to content

The implementation in C++ of the closest-pair doubling algorithm which finds the smallest distance between two points in a metric space in O(n log n) time without directly using the points' coordinates.

License

Notifications You must be signed in to change notification settings

ThangMinhCao/closest-pair-doubling

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

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

License

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

About

The implementation in C++ of the closest-pair doubling algorithm which finds the smallest distance between two points in a metric space in O(n log n) time without directly using the points' coordinates.

Topics

Resources

License

Stars

Watchers

Forks

Languages