# 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? –  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
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

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.

-
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.

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