Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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? –  joriki Apr 12 '12 at 13:51
    
I suspect what you want is a minimal 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. –  Henning Makholm Apr 12 '12 at 13:52
1  
Have you heard about Steiner tree? –  dtldarek Apr 12 '12 at 15:24
    
@joriki I edited the description. I always add all the points before I start connecting them. –  pgsandstrom Apr 12 '12 at 18:03
    
@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. –  pgsandstrom Apr 12 '12 at 18:06

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
This seems to be the best solution. Thank you! –  pgsandstrom Apr 13 '12 at 9:10

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.

share|improve this answer
    
Indeed, you are right. Obviously I should cache those values! Thanks! :) –  pgsandstrom Apr 12 '12 at 19:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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