Show Search Range Show left and right closest pairs

Shown above is an interactive simulation of a recursive algorithm for finding the closest pair of points in a plane. You could attain this result in O(n ** 2) time with a simple brute force, but the clever recursion in O(n log(n)) time is much nicer!

You can click either of the two buttons above to see the recursive stitching range and the left and right closest pairs from the top level of the recursion. To understand what these are, you can read about the algorithm at one of the references below.

This implementation also prevents you from imputting points with the same x or y coordinate as other points to avoid the need for random rotation (which would otherwise be used to enfore this property), so if you ever experience any awkwardness clicking new points, then that's probably why.

For more information, see here and here and maybe also here. The code is on github.