closestpair

Closest pair refers to the closest pair problem in computational geometry. Given a finite set of points in the plane (or in higher-dimensional space), the goal is to find two points whose Euclidean distance is minimal. The problem can be defined for other distance metrics as well, but the Euclidean version is the most common.

A straightforward solution computes all pairwise distances and keeps track of the smallest one. This naive approach runs in O(n^2) time and is practical only for small inputs. More sophisticated algorithms reduce the running time significantly, with the two-dimensional case achieving O(n log n) time.

The most widely cited method is a divide-and-conquer algorithm. It works by sorting points by x-coordinate, splitting the set into two halves, and recursively finding the closest pairs in each half. Let delta be the minimum distance found in the halves. The algorithm then checks a vertical strip of points within delta of the split line, sorting the strip by y-coordinate and comparing each point with a small, constant number of following points. This merge step can be done in linear time, yielding an overall O(n log n) algorithm. The approach was introduced by Shamos and Hoey and has influenced many practical implementations.

Extensions and variants include higher-dimensional closest pair problems, which generalize the same idea but with higher time complexities, and dynamic or online versions where points are added or removed. Other variants explore alternate distance metrics or approximate solutions for large data sets.

Applications span collision detection, pattern recognition, clustering pre-processing, and geographic information systems.