Member-only story
Finding Closest Points Faster Than O(n²)
An interesting application of the divide-and-conquer paradigm
Imagine that you work in air traffic control. To make sure that no airplanes collide, you monitor their positions and give a warning signal to the airplanes that are closest together.

Since you have to conduct this check every few seconds, you want to do it automated and as fast as possible. One way to achieve your goal is by computing the distances between all pairs of airplanes and picking the ones that are closest together. If there are n airplanes, this results in an O(n²) algorithm. While this is alright, we can do better than this, and in this article, I will show you how.
Closest Points in the Euclidean Norm
Ah idealized version of the use case from above is to find points that are closest to each other in Euclidean distance. It is a classic problem from algorithmic geometry that can also be used in other contexts, such as computer vision and robotics.