Euclidean Minimal Spanning Tree and Delaunay Triangulation

Question

I want to calculate the minimal spanning tree based on the euclidean distance between a set of points on a 2D-plane. My current code stores all the edges, and then performs Prim's algorithm in order to get the minimal spanning tree. However, I am aware that doing this takes O(n^2) space for all the edges.

After doing some research, it becomes clear that the memory and runtime can be optimized if I calculate the delaunay triangulation first on this set of points, then obtain the minimal spanning tree via running Prim's or Kruskal's algorithm on the edges of the triangulation.

This is part of a programming contest (https://prologin.org/train/2017/qualification/taxi_des_neiges), so I doubt I'd be able to use scipy.spatial. Is there any alternatives to simply get the edges contained in the Delaunay triangulation?

Thanks in advance.

Answer 1

Would a module help? Here's a few that might work:

• delaunator
• poly2tri
• triangle
• matplotlib?

Roll your own? Both of these describe the incremental algorithm, which Wikipedia seems to say is O(n log n):

• http://www.geom.uiuc.edu/~samuelp/del_project.html
• http://graphics.stanford.edu/courses/cs368-06-spring/handouts/Delaunay_1.pdf

Here's an ActiveState recipe that might help to get started, but it looks like it's not finished.

Answer 2

It looks like Scipy uses QHull, which.. somewhere in this folder... has the code for performing the delaunay triangulation and getting the edges (albeit implemented in C)

https://github.com/scipy/scipy/tree/master/scipy/spatial/qhull/src