Cheap and Secure Web Hosting Provider : See Now

# Algorithm for converting (coordinates + reach radius) data to directed graph

, ,
Problem Detail:

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 < Ri < 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!

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

Best Answer from StackOverflow

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

3200 people like this

#### Post a Comment

Let us know your responses and feedback