**Problem Detail:**

I am trying to find a solution better than O(n^{2}) for the following problem:

There are N points on a 2-D plane (N $\le$ 10^{6}), with integer coordinates between -10^{5} and 10^{5}. Each point has an associated integer "reach radius" R_{i} (0 < R_{i} < 10^{5}).

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$ R_{A}).

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!

###### Asked By : Arnold Beiland

###### Answered By : Arthelais

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) > 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.

Question Source : http://cs.stackexchange.com/questions/65496

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback