3
$\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

  • 1
    What does "to minimize the length of each individual line" mean? From the description of your current algorihtm, it seems that you want to minimize the length of the segments that get added as you add the points one by one. Are you aware that the result may depend on the order in which you add the points?2012-04-12
  • 0
    I suspect what you want is a [minimal spanning tree](http://en.wikipedia.org/wiki/Minimum_spanning_tree), though wanting to "minimize the length of _each_ connecting line" sounds impossibly ambitious. A mimimal spanning tree minimises the _sum_ of all the lengths instead.2012-04-12
  • 1
    Have you heard about [Steiner tree](http://en.wikipedia.org/wiki/Steiner_tree_problem)?2012-04-12
  • 0
    @joriki I edited the description. I always add all the points before I start connecting them.2012-04-12
  • 0
    @HenningMakholm the problem with MST-like solutions is that then I would need to create a complete graph, i.e. where all nodes are connected to each other. Given those calculations, I don't think the algorithm would get faster.2012-04-12
  • 0
    By definition, a spanning tree connects all nodes to each other. As you describe it, to add planet $n$, you have to check $n-1$ distances, which gives an $O(n^2)$ algorithm2012-04-12
  • 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