hgeometry- Geometric Algorithms, Data structures, and Data types.

Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone



\(O(n\log n)\) time algorithm algorithm to compute the Euclidean minimum spanning tree of a set of \(n\) points in \(\mathbb{R}^2\).



euclideanMST :: (Ord r, Fractional r) => NonEmpty (Point 2 r :+ p) -> Tree (Point 2 r :+ p) Source #

Computes the Euclidean Minimum Spanning Tree. We compute the Delaunay Triangulation (DT), and then extract the EMST. Hence, the same restrictions apply as for the DT:

pre: the input is a *SET*, i.e. contains no duplicate points. (If the input does contain duplicate points, the implementation throws them away)

running time: \(O(n \log n)\)