3
$\begingroup$

Given a set of $n$ two-dimensional points in the plane $$\{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\}$$ and a real number $M$, I want to transform this set of points into a graph with the points as vertices with an edge between points $A$ and $B$ if the distance between $A$ and $B$ is at most $M$.

What is a fastest algorithm that can perform this task?

$\endgroup$
1
  • $\begingroup$ One thing to note is that if $M$ is very very large, then you need to create all m ~ n² pairs, so you cannot guarantee that you don't need to perform n² operations. Hence, if you're constructing the actual graph, a linear time algorithm (in the number of points) is not possible. $\endgroup$
    – Pål GD
    Jan 15, 2020 at 16:16

1 Answer 1

2
$\begingroup$

As you can imagine, evaluating every pair of points is very expansive ($O(N^2)$ for $N$ points).

If your set of point is sufficiently dense with respect to $M$, a simple solution is to use a grid. Build a grid of $M \times M$ cells, then for each cell, compute the list of points inside (doing one loop on points $O(N)$). Finally you just have to compare every point with every other point in the same cell or in one of the 8 surrounding it.

If you set of points is very dense you even can use a second grid of $\frac{M}{\sqrt{2}} \times \frac{M}{\sqrt{2}}$ cells so the points in the same cells have necessarly pair-wise distance lower than $M$. This may save some computation.

Note that in the case you have lot of empty cells (small density), it may generate memory issue. Imagine for instance 2 pairs of points very distant to each other (with respect to $M$). It may require a tremendeous grid, just to process 4 points... In this case, the basic "all-pair" comparison would be largely more efficient. k-d tree may be a solution to this problem. Or you can either identify the empty zones to process the points subset by subset.

$\endgroup$
2
  • 2
    $\begingroup$ What is the suggested algorithm and what is its complexity? $\endgroup$
    – Pål GD
    Jan 15, 2020 at 16:12
  • $\begingroup$ @Pål_GD Basically, I suggest the $M \times M$ cell grid algorithm. And of course, you cannot guarantee that it will do better than $O(N^2)$ or even worse in the low density case. The remain of my answer try to treat extreme cases. $\endgroup$
    – Optidad
    Jan 16, 2020 at 10:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.