# Mark Needham

Thoughts on Software Development

One of the algorithms covered in Algo Class was the closest pairs algorithm – an algorithm used to determine which pair of points on a plane are closest to each other based on their Euclidean distance.

My real interest lies in writing the divide and conquer version of the algorithm but I started with the brute force version so that I’d be able to compare my answers.

This is the algorithm:

```minDist = infinity for each p in P: for each q in P: if p ≠ q and dist(p, q) < minDist: minDist = dist(p, q) closestPair = (p, q) return closestPair```

‘infinity’ in this case could be the maximum value that an Int could hold which on a 64 bit architecture would be 263 so I hardcoded that into my implementation:
o

```bfClosest :: (Ord a, Floating a) => [(a, a)] -> Maybe ((a, a), (a, a)) bfClosest pairs = snd \$ foldl (\ acc@(min, soFar) (p1, p2) -> if distance p1 p2 < min then (distance p1 p2, Just(p1, p2)) else acc) (2^63, Nothing) [(pairs !! i, pairs !! j) | i <- [0..length pairs - 1], j <- [0..length pairs-1 ], i /= j] where distance (x1, y1) (x2, y2) = sqrt \$ ((x1 - x2) ^ 2) + ((y1 - y2) ^ 2)```

We’re comparing each point with all the others in the list by folding over a collection of all the combinations and then passing the pair with the smallest distance between points as part of our accumulator.

More by chance than anything else I was reading the Learn You a Haskell chapter on types and type classes and came across the maxBound function which does exactly what I want:

```> 2 ^ 63 9223372036854775808   > maxBound :: Int 9223372036854775807```

We can’t plug that straight into the function as is because the fold inside ‘bfClosest’ expects a float and had been automatically coercing 263 into the appropriate type.

We therefore use ‘fromIntegral’ to help us out:

```bfClosest :: (Ord a, Floating a) => [(a, a)] -> Maybe ((a, a), (a, a)) bfClosest pairs = snd \$ foldl (\ acc@(min, soFar) (p1, p2) -> if distance p1 p2 < min then (distance p1 p2, Just(p1, p2)) else acc) (fromIntegral (maxBound :: Int), Nothing) [(pairs !! i, pairs !! j) | i <- [0..length pairs - 1], j <- [0..length pairs-1 ], i /= j] where distance (x1, y1) (x2, y2) = sqrt \$ ((x1 - x2) ^ 2) + ((y1 - y2) ^ 2)```
Be Sociable, Share!

Written by Mark Needham

May 7th, 2012 at 9:18 am