Efficiently obtain the graph from given facts
An answer to this question on Stack Overflow.
Question
I have a set of points in 2-D plane(xy) say n points.
(x1, y1), (x2, y2), (x3, y3), ......................., (xn, yn)
My objective is to draw a graph. Two nodes(points) in the graph will be connected iff
abs(difference in x coordinate) + abs(difference in y coordinate) = L(given).
It can be done O(n*n). Is it possible to do it efficiently.
BTW I am trying to solve this problem
Answer
It is certainly possible to do it efficiently given certain assumptions about the data. I'll think about more general cases. If, for instance, the points are distributed homogeneously and the interaction distance L(given) is small relative to the spread of the data then the problem can be converted to O(n) by binning the particles.
This takes you from the situation on the left to the situation on the right:
The bin size is taken to be >=L(given) and, for any particle, the particle's bin and the 8 neighbouring bins are all searched. If the number of particles in a bin averages a constant d, then the problem is solvable in O(9dn)=O(n) time.