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

Algorithms.Geometry.EuclideanMST.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

# 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)$$