Skip to content

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

License

Notifications You must be signed in to change notification settings

AndrewB330/EuclideanMST

Repository files navigation

EuclideanMST

Generic badge

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