You don't brute force compare against all points in Y'
but only against the one next to p
. If that one is already too far away you can just stop, because all other points will be even further away. You only continue evaluating the next closest neighbor if the last one was still within your search distance.
The text explains it in the As we will see shortly section.
Sorting is an optimization here that allows you to iterate nearest neighbors in O(1)
after paying the sorting costs of O(n log n)
once.