Let's look at a neat problem that appears harder than it looks at first (well, for computers, it still might take a bit of work for us). First, an important definition.
The Euclidean distance between two points $p_1 = (x_1,y_1)$ and $p_2 = (x_2,y_2)$ is defined by \[d(p_1,p_2) = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}.\]
Of course, one can define many different kinds of distances on many kinds of objects. So now we can ask the following question.
The closest points on a plane problem is: Given a list of $n$ points on a plane, find the closest pair of points.
This is a fairly simple problem that is another one of those things that people probably really want to know about and efficiently, since it's a very basic computational geometry problem and has obvious applications in all sorts of graphics and computer vision problems. It was first studied by Shamos and Hoey in 1975, where they showed the algorithm we're about to investigate.
We will assume that squaring and square roots are basic operations (although we don't really need to take square roots). There is a pretty obvious brute force algorithm: just compute and check the distance of every pair of points. Of course, if you have $n$ points, that's $O(n^2)$ things you have to check.
So we want to try to use divide and conquer on this set, ideally splitting our problem up into subproblems of roughly equal size. It's not exactly clear how to do this, which can lead to something complicated like splitting our space into quadrants or something.
Luckily, we do not need to go that far. Something simpler we can do is to just split our problem into two. First, we sort our points by their $x$-coordinate and then divide our points accordingly. Picture a vertical line $L$ going down the middle of the space. Then we recursively find the closest pair in each half and choose the closer of the two. Once we get down to three points in our space, we can just compute which pair is closest. Easy! But there is a big complication with this strategy:
What happens if the closest pair is actually right in the middle, with one point to the left and one point to the right?
Surprisingly, all is not lost. Let $\delta$ be the smaller of the distances computed for the left closest pair and the right closest pair. If we run into the edge case that we described, we know that this pair can't be more than $\delta$ away from each other!
What we can do is consider only those points that are at most $\delta$ away from the line $L$. Sort these by their $y$-coordinates. The next question is: how many comparisons do we have to make when considering these points? It seems like we could be looking at arbitrarily many such comparisons, but we can do a bit more narrowing down.
Let $S = \{p_1, \dots, p_k\}$ be the set of points within distance $\delta$ of line $L$, sorted in order of $y$-coordinate. Then, for each point $p_i$, if $p_j$ with $|i - j| \gt 7$, then $d(p_i,p_j) \gt \delta$.
Consider a rectangle $R$ of width $2\delta$ and height $\delta$ centered on $L$. We claim that this rectangle can contain at most 8 points. If it contains more, then there are enough points on one side of $L$ so that there is at least one pair of points with distance closer than $\delta$, which would contradict our assumption that $\delta$ was the distance of the closest pair of points on one side.
To see this, we divide $R$ into eight squares of length and width $\frac \delta 2$. We claim that each square can contain at most one point. Observe that the furthest apart any two points can be in such a square is $\frac{\delta}{\sqrt 2} \lt \delta$.
Therefore, for any point within the $\delta$-region of $L$, it suffices to compare it with at most seven other points, since all other points are guaranteed to have distance greater than $\delta$. The important thing about this is we only need to compare it with a constant number of points (it is possible to improve the constant from seven by employing more complicated geometric arguments). So even if we end up with an unusually large number of points along this strip, we know that at worst, we need something on the order of $O(n)$ comparisons, which crucially doesn't take us out of the realm of $O(n \log n)$.
So a very general description of our algorithm is as follows:
This is enough to prove that our algorithm is correct. Just like with Mergesort, this involves first proving the combining step is true (which we just did above) and then proving that the algorithm itself is correct via an inductive argument. In this case, the base case would be when we need to determine the closest pair of 3 points.
An efficient implementation almost follows from what we've just described. The only complication occurs in the combining phase, when we try to examine points along the middle strip. As we've described the algorithm, we would require sorting points by their $y$-coordinate each time we want to combine solutions. This leads to an $O(n \log n)$ step at each recursive call, so we need to avoid this.
It turns out the trick is in preprocessing and keeping two copies of the points: one sorted by $x$-coordinate and one sorted by $y$-coordinate. Once we do this, we can just extract the points we need in order by referring to these two lists. This then gets us the following algorithm.
\begin{algorithmic}
\PROCEDURE{closest-pair}{$S = \{p_1 = (x_1, y_1), \dots, p_n = (x_n,y_n)\}$}
\STATE $S_x = $ $S$ sorted by $x$-coordinate
\STATE $S_y = $ $S$ sorted by $y$-coordinate
\RETURN{\CALL{closest-pair-rec}{$S_x,S_y$}}
\ENDPROCEDURE
\PROCEDURE{closest-pair-rec}{$S_x, S_y$}
\IF{$n \leq 3$}
\STATE Compute closest pair
\RETURN{Closest pair}
\ENDIF
\STATE Construct $L_x,L_y,R_x,R_y$
\STATE $(\ell_1,\ell_2) = $ \CALL{closest-pair-rec}{$L_x,L_y$}
\STATE $(r_1,r_2) = $ \CALL{closest-pair-rec}{$R_x,R_y$}
\STATE $\delta = \min(d(\ell_1,\ell_2),d(r_1,r_2))$
\STATE $L = \max_{(x,y) \in L_x} x$
\STATE $M = \{(x,y) \in S_y \mid |x - L| \leq \delta\}$, sorted by $y$-coordinate
\FORALL{$p \in M$}
\STATE Compute $d(s,s')$ for next 7 points $s' \in M$
\ENDFOR
\STATE Let $s,s'$ be the pair of minimum distance computed among points of $M$
\IF{$d(s,s') \lt \delta$}
\RETURN{$(s,s')$}
\ELIF{$d(\ell_1,\ell_2) \lt d(r_1,r_2)$}
\RETURN{$(\ell_1,\ell_2)$}
\ELSE
\RETURN{$(r_1,r_2)$}
\ENDIF
\ENDPROCEDURE
\end{algorithmic}
This algorithm is a bit more complicated than ones we've seen before, so this proof will be a bit more exhaustive.
Closest-Pair has running time $O(n \log n)$.
First, the sorting steps of lines 2 and 3 can be done in $O(n \log n)$ time. We then need to analyze the running time for Closest-Pair-Rec. Let $T(n)$ be the number of operations performed by Closest-Pair-Rec. When $n \leq 3$, we have $T(n) = O(1)$.
Now, consider when $n \gt 3$.
Therefore, we have the recurrence \[T(n) = \begin{cases} O(1) & \text{if $n \leq 3$}, \\ T(\lfloor n/2 \rfloor) + T(\rceil n/2 \rceil) + O(n) & \text{if $n \gt 3$.} \end{cases}\] and we have that $T(n) = O(n \log n)$.
Then the running time of Closest-Pair is $O(n \log n) + T(n) = O(n \log n)$.
A formal standalone proof of this would involve proving the recurrence for $T(n)$. Of course, this is the same recurrence as Mergesort, so that's not too hard.