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

Algorithms.Geometry.ClosestPair.Naive

Description

Naive O(n^2)) time algorithm to compute the closest pair of points among $$n$$ points in $$\mathbb{R}^d$$.

Synopsis

# Documentation

closestPair :: (Ord r, Arity d, Num r) => LSeq 2 (Point d r :+ p) -> Two (Point d r :+ p) Source #

Naive algorithm to compute the closest pair according to the (squared) Euclidean distance in $$d$$ dimensions. Note that we need at least two elements for there to be a closest pair.

running time: $$O(dn^2)$$ time.

closestPairWith :: Ord r => DistanceFunction (Point d r :+ p) -> LSeq 2 (Point d r :+ p) -> SP (Two (Point d r :+ p)) r Source #

Naive algorithm to compute the closest pair of points (and the distance realized by those points) given a distance function. Note that we need at least two elements for there to be a closest pair.

running time: $$O(T(d)n^2)$$, where $$T(d)$$ is the time required to evaluate the distance between two points in $$\mathbb{R}^d$$.

type DistanceFunction g = g -> g -> NumType g Source #