0
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Where does this problem come from? It looks a lot like a programming competition problem, for example. (If you only have a million points, a quadratic algorithm will almost certainly solve the problem overnight, for example.) $\endgroup$ Commented Nov 3, 2016 at 15:47
  • 1
    $\begingroup$ Yes this came to mind while trying to figure out a competition problem, which could be solved in linear time if I had the graph instead of the points. $\endgroup$ Commented Nov 3, 2016 at 19:53

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for pointing out the O(N^2) lower bound. I seem to have forgotten that there could be O(N^2) edges and then the whole struggle is kind of useless... $\endgroup$ Commented Nov 3, 2016 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.