Manhattan distance algorithm job interview question

Given a set of n p开发者_高级运维oints in an X-Y plane, how can I determine if every point is at least separated by every other point by a Manhattan distance of 5 units in time less than O(n^2)?

What is the best algorithm to implement this?

Thank you.

1. Sort the points by x. This takes time 'O(n log(n))'.

2. Divide the range into strips of width 10. (You'll need an obvious bit of care here for the pathological case where one point has x-coordinate 1 and the next has x-coordinate 10²⁰.) O(n)

3. For each strip:

   1. Take the set of points within that strip, or within an x of 5 to either side, and sort them by y. This is O(n log(n)) across all strips.
   2. For each point in the strip, find the Manhattan distance to all other points in that slightly wider strip whose y coordinate is within 5 of their own. If you find any within distance 5, exit and report false. This is O(n) across all strips.

4. Report true.

This algorithm is O(n log(n)). I strongly advise that you demonstrate for yourself that the pointwise Manhattan comparison in 1.2 takes O(n) operations, even if the answer is false.

For true it is simple - it follows from the fact that there is a maximum number of other points that can be squeezed in a 20x10 box without 2 getting within 5. For false it is trickier, you can have a lot of other points in that box, but by the time you have compared a fixed number of them to the rest, you must have found two within distance 5. Either way a given point participates in a fixed maximum number of point to point comparisons before you have your answer.