EuclideanMST

Implementations of different algorithms for building Euclidean minimum spanning tree in k-dimensional space.

Algorithms:

• EMST using Kd-tree O(NlogN)*
  • Implementation of algorithm described in "Fast Euclidean Minimum Spanning Tree: Algorithm, Analysis, and Applications. William B. March, Parikshit Ram, Alexander G. Gray"*
  • For higher dimensions (5D and more) and small number of points it can work even slower than Prim's algorithm*
• Prim's algorithm O(N^2)
  • Straightforward MST on fully connected Euclidean graph

How to add to your project

You can use standalone header file from standalone_header/ folder, or you can add this project as a CMake subdirectory:

add_subdirectory(EuclideanMST)
target_link_libraries(<TARGET_NAME> EuclideanMST)

How to use

    std::vector<Point<3>> points(n); // your data
    // read data ...
    // you can acces any Point<> dimension by index
    // e.g. cin >> points[i][0] >> points[i][1] >> points[i][2]; 
    
    KdTreeSolver<3> solver(points);
    
    double total_length = solver.get_total_length();
    std::vector<Edge> edges = solver.get_solution(); 
    // Edge is std::pair<size_t, size_t> - describes connected pair

Benchmarks:

Dimensions	Number of points	Kd-tree	Prim
2	50'000	0.24 sec	29.0 sec
3	50'000	0.67 sec	32.0 sec
4	50'000	1.59 sec	36.0 sec
2	10'000'000	69.0 sec	~10+ days
3	10'000'000	186.0 sec	~13+ days
4	10'000'000	673.9 sec	~15+ days
5	180'000	15.3 sec	~300+ sec

Contribution

Very appreciated

TODO:

• Implement EMST using Cover-tree
• More use-cases
• Online-solver
• Parallel implementation using OMP (actually had some experiments here, this algorithm can be parallelized quite well)
• Other...