# Connecting all points on a plane with shortest path possible

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? • 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? Apr 12, 2012 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. Apr 12, 2012 at 13:52
• Have you heard about Steiner tree? Apr 12, 2012 at 15:24
• @joriki I edited the description. I always add all the points before I start connecting them. Apr 12, 2012 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. Apr 12, 2012 at 18:06

You're describing the standard Euclidean minimum spanning tree problem, which can be solved in $O(n\log n)$ time using Delaunay triangulations.
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.