CareerCup

Thanks for posting an Intel question. I'm considering applying there in the future so I appreciate your post ron.

Even your simple solution is wrong. Manhattan distance is defined as abs(x1-x2)+abs(y1-y2), not separately.

The best i can think of is O(nlogn). Just find the Manhattan distances of each point from (0,0) and put in array. Sort the array and check that adjacent pair values are greater than 5.

Sort the points first based on x co-ordinates.Time:O(nlogn)
For every point,check if the difference of x coordinates between that point and its immediate neighbours is greater than 5.Time:O(n)
Do the same for y co-ordinates.Overall Time complexity:O(nlogn)

I guess a sweep line algorithm might work as someone has suggested.. Could someone elaborate this and give me an idea of how it can be implemented for this particular problem.

I hope this works in O(n logn) time. Plz dig into the solution, and point any possible flaws. Thanks.

1. let the points are represented in a sorted manner in a matrix p[N][N] such that
(a)in row i, each point has same x co-ordinate; sorted by y co-ordinate values
(b)rows are sorted based on x co-ordinate values, i.e. row (i+1)'s x co-ordinate > row (i)'s x co-ordinate
=> time: O(n logn)

2. For every point (x,y) compute the set S of points which lie in the open range (x-5, y-5). As points are sorted, it can be done in O(log n). Test if any point of S has less than 5 manhattan-distance (MD) wrt (x,y). If one exists, terminate the computation; and return FALSE. Otherwise, proceed with next point.
=> time: O(n logn)

3. This is the crucial argument. To grasp it, it's better to work on paper.
If it could happen that in each open range (x-5,y-5) for each point (x,y) there could be O(n) points in S, then effectively it'd be O(n^2) complexity.

But, the good is that it won't be the case. Each point Q(x',y') can be in at most 4 open ranges for 4 points, say, A,B,C,D (each of them have a MD >= 5, otherwise if MD(A,B) < 5, it'll return FALSE). The reason is that if Q lies in range (Ax-5,Ay-5), but not inside the square region denoted by 4 points (Ax+5, Ay), (Ax, Ay+5), (Ax-5, Ay), (Ax, Ay-5); then it could exist at maximum three other points (B,C,D)'s ranges, but not have a MD < 5 wrt either of B, or C, or D.

This argument establishes that in the worst case, maximum 4n points to be checked for the given n points. This ensures O(log n) per point complexity in an amortized sense.

how abt this simple approach?

X[1..n] y[1..n] given array for cordinates (x1,y1) ....(xn....yn)

step 2) sort by X cordinates. for each index change of X do a corresponding change in Y. this preserves (xi,yi) cordinates.. ie same index in each array means cordinates of same point

step 3)
now calculate Xdiff[1..n-1]
for x1 will have only one adjacent point and xn will also have one adj point. rest will have 2 adj points. Similarly calculate Ydiff[1.. n-1];

step 3) calculate by iteration thru Xdiff minimum manhatten distance b/w each alternate pair. handle 1st index and last index properly

manhatten[i] = min (xdiff[i-1]+ydiff[i-1], xdiff[i+1]+ydiff[i+1])
if any of manhatten[i] is less than 5 return

time complexity O(nlogn)

we can make use of voronoi diagram. The construction will take O(nlgn) and will require O(n) space. Using this diagram we can find the nearest neighbor of each point in O(lgn). Now we can iterate linearly over each point finding its nearest neighbor. If we find a point whose nearest neighbor is less than at Manhattan Distance of 5 Units then we return False. Finding n nearest points takes O(nlgn).

We can also use the algorithm to find the closest pair of points using the divide and conquer approach. This runs in O(nlogn) time.

cs.umd.edu/class/fall2009/cmsc451/lectures/Lec09-closepoints.pdf

i think i can make O(n): 2 vectors. one for y one for x. each cell in x holds a set of y values of point on that x, or -1 if no points. and the same for y. so each point is represented twice.
now, we go over all x, and for each point we need to scan a rectangular area of 4X4 around that point and make sure there are no points there.

Guys another solution nlogn
1. Calculate the Manhattan distance of each point from (0,0) and make a min heap (nlogn)
2. Remove the top element and heapify the heap again (logn)
3. Remove the next min element
4. Take a diff of the above two least min elements and got the minimal distance elements.
5. if this distance is < 5 then return FALSE else TRUE

use ball tree