Member-only story

Finding Closest Points Faster Than O(n²)

An interesting application of the divide-and-conquer paradigm

Dr. Robert Kübler
All About Algorithms
8 min readJan 5, 2024

--

Photo by softmarmotte on Unsplash

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.

From https://www.flightradar24.com/33.96,132.61/8, 11:43am GMT+1, 5th of December 2023. Image by the author.

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.

--

--

Published in All About Algorithms

From intuitive explanations to in-depth analysis, algorithms come to life with examples, code, and awesome visualizations.

Written by Dr. Robert Kübler

Studied Mathematics, PhD in Cryptanalysis, working as a Data Scientist. Check out my new publication! https://allaboutalgorithms.com

Responses (6)

What are your thoughts?