Solution: Closest Points

Solution

This computational geometry problem has many applications in computer graphics and vision. A naive algorithm with quadratic running time iterates through all pairs of points to find the closest pair. Our goal is to design an $O(n\cdot$$log(n))$ time divide-and-conquer algorithm.

To solve this problem in time $O(n$$\cdot$$log(n))$, let’s first split the given $n$ points by an appropriately chosen vertical line into two halves, $S_{1}$ and $S_{2}$, of size $\frac{n}{2}$ (assume for simplicity that all $x$-coordinates of the input points are different). By making two recursive calls for the sets $S_{1}$ and $S_{2}$, we find the minimum distances $d_{1}$ and $d_{2}$ in these subsets. Let $d$ = min{$d_{1}$, $d_{2}$}.