Finding Closest Points Faster Than O(n²)
<p>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 <strong>closest together</strong>.</p>
<p><img alt="" src="https://miro.medium.com/v2/resize:fit:700/1*r_qs4T0SzYMm5_i6GnrdfQ.png" style="height:513px; width:700px" /></p>
<p>From <a href="https://www.flightradar24.com/33.96,132.61/8" rel="noopener ugc nofollow" target="_blank">https://www.flightradar24.com/33.96,132.61/8</a>, 11:43am GMT+1, 5th of December 2023. Image by the author.</p>
<p>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 <em>n</em> airplanes, this results in an <em>O</em>(<em>n</em>²) algorithm. While this is alright, we can do better than this, and in this article, I will show you how.</p>
<p><a href="https://allaboutalgorithms.com/finding-closest-points-faster-than-o-n%C2%B2-ea5d005bc911"><strong>Learn More</strong></a></p>