Note that the first official editorial (partition the plane to a grid of \(K \times K\) square packets) is the second half of Rabin’s closest pair algorithm. The first half is sampling of \(N\) randomly-picked pairs and picking their minimum distance \(K\). With high probability \(O(N)\) pairs should have distance \(\le K\), and the rest proves that the algorithm completes in \(O(N)\) overall.