Algorithm for converting (coordinates + reach radius) data to directed graph I am trying to find a solution better than O(n2) for the following problem: 

There are N points on a 2-D plane (N $\le$ 106), with integer coordinates between -105 and 105. Each point has an associated integer "reach radius" Ri (0 &lt; Ri &lt; 105). 

Build a directed graph (represented by adjacency lists) in which these points are the vertices and there is an edge from A to B if and only if point B falls in the reach of point A (i.e. euclidean_distance(A,B) $\le$ RA). 

I am thinking of dividing the plane into 4 equal regions, and solving the same problem for the regions, but don't know how to combine the partial solutions...

Thanks in advance for any ideas!
If all pairs of points are within each other's reach, you can not optimize the construction below $O(N^2)$. However, you can optimize for sparser graphs by ordering pairs of points by distance from smallest distance to largest. Once you find a pair $(A, B)$ where $d(A, B) &gt; R_{max}$, you are done. A technique you can use for this can be found here. This technique makes use of divide and conquer.

This is more a heuristic. I do not think there is a way (with or without use of divide and conquer) to reduce the worst case complexity.