Closest Pair of Points Problem - Brute-force Algorithm

Brute-force Algorithm

The closest pair of points can be computed in O(n2) time by performing a brute-force search. To do that, one could compute the distances between all the n(n − 1) / 2 pairs of points, then pick the pair with the smallest distance, as illustrated below.

minDist = infinity for i = 1 to length(P) for j = i + 1 to length(P) let p = P, q = P if dist(p, q) < minDist: minDist = dist(p, q) closestPair = (p, q) return closestPair