| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.EuclideanMST
Description
\(O(n\log n)\) time algorithm algorithm to compute the Euclidean minimum spanning tree of a set of \(n\) points in \(\mathbb{R}^2\).
Synopsis
- euclideanMST :: (Ord r, Fractional r) => NonEmpty (Point 2 r :+ p) -> Tree (Point 2 r :+ p)
Documentation
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)\)