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:
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 scot-free, click here to see the proof).
Well this is simply fantastic news, because now we don't need to check all
n2 points. All we have to do is sort the points in the
strip by their y-coordinates 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.
- those points within d of p in the direction of the other
- those within d of p in the positive and negative
However, since we sorted the points in the strip by their
y-coordinates the process of merging our two subsets is not
linear, but in fact takes O(nlogn) time.