Algorithms.Geometry.ClosestPair.DivideAndConquer

Classical \(O(n\log n)\) time divide and conquer algorithm to compute the closest pair among a set of \(n\) points in \(\mathbb{R}^2\).

Documentation

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

Classical divide and conquer algorithm to compute the closest pair among \(n\) points.

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

type CP q r = Top (SP (Two q) r)

the closest pair and its (squared) distance

data CCP p r

Type used in the closest pair computation. The fields represent the points ordered on increasing y-order and the closest pair (if we know it)

Constructors

CCP (NonEmpty (Point 2 r :+ p)) !(CP (Point 2 r :+ p) r)

Instances

(Eq r, Eq p) => Eq (CCP p r)

Defined in Algorithms.Geometry.ClosestPair.DivideAndConquer

Methods

(==) :: CCP p r -> CCP p r -> Bool

(/=) :: CCP p r -> CCP p r -> Bool

(Show r, Show p) => Show (CCP p r)

Defined in Algorithms.Geometry.ClosestPair.DivideAndConquer

Methods

showsPrec :: Int -> CCP p r -> ShowS

show :: CCP p r -> String

showList :: [CCP p r] -> ShowS

(Num r, Ord r) => Semigroup (CCP p r)

Defined in Algorithms.Geometry.ClosestPair.DivideAndConquer

Methods

(<>) :: CCP p r -> CCP p r -> CCP p r

sconcat :: NonEmpty (CCP p r) -> CCP p r

stimes :: Integral b => b -> CCP p r -> CCP p r

mergePairs

Arguments

:: forall p r. (Ord r, Num r)

=> CP (Point 2 r :+ p) r

current closest pair and its dist

-> NonEmpty (Point 2 r :+ p)

pts on the left

-> NonEmpty (Point 2 r :+ p)

pts on the right

-> CP (Point 2 r :+ p) r

Function that does the actual merging work