
Thankfully, we can make another life saving observation at this point. For
any particualr point p in one strip, only points that meet the
following constraints in the other strip need to be checked:
 those points within d of p in the direction of the other
strip
 those within d of p in the positive and negative
y directions
Simply because points outside of this bounding box cannot be less than
d units from p (see
figure 3.3). It just so
happens that because every point in this box is at least d apart,
there can be at most six points within it (I won't let myself get
away with that scotfree, click here to see the proof).
Well this is simply fantastic news, because now we don't need to check all
n^{2} points. All we have to do is sort the points in the
strip by their ycoordinates and scan the points in order, checking
each point against a maximum of 6 of its neighbors. This means at most
6*n comparisons are required to check all candidate pairs.
However, since we sorted the points in the strip by their
ycoordinates the process of merging our two subsets is not
linear, but in fact takes O(nlogn) time.
