4
$\begingroup$

I want to connect N nodes, so all are connected, by connecting each node to their closest neighbors. An image of what I'm looking for is below.

Currently I solve it like this: I add a random node to a set called the "connected nodes"-set. Then I find the closest node not in the set to any node in the "connected nodes"-set, and and add it to the set by connecting the two nodes. The problem is that for each node I want to add, I have to check the distance for each node in the set to each node not in the set. The result is a complexity of O(n^3). Is there a way to decrease this complexity?

enter image description here

  • 0
    @sandis: "Minimal spanning tree" is not a _solution_; it is a conventional description of what your _problem_ is. Knowing its name should help you in searching for solutions.2012-04-12

2 Answers 2

5

You're describing the standard Euclidean minimum spanning tree problem, which can be solved in $O(n\log n)$ time using Delaunay triangulations.

See Joe O'Rourke's textbook Computational Geometry in C for details.

  • 0
    This seems to be the best solution. Thank you!2012-04-13
3

You're essentially running Prim's algorithm. It has a complexity of $O(|V|^2)$, so I would check your implementation.

In particular, if a point outside the connected set $S$ doesn't get picked in one iteration, you seem to be unnecessarily recomputing its distances to all the points in $S$ all over again in the next iteration. What you should do is remember, for each point outside $S$, its closest point in $S$. Then when you add a point to $S$, you just have to check whether it is closer to the remembered closest point and update the latter if necessary.

  • 0
    Indeed, you are right. Obviously I should cache those values! Thanks! :)2012-04-12