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...