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

$\endgroup$
7
  • 1
    $\begingroup$ 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? $\endgroup$
    – joriki
    Apr 12, 2012 at 13:51
  • $\begingroup$ 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. $\endgroup$
    – hmakholm left over Monica
    Apr 12, 2012 at 13:52
  • 1
    $\begingroup$ Have you heard about Steiner tree? $\endgroup$
    – dtldarek
    Apr 12, 2012 at 15:24
  • $\begingroup$ @joriki I edited the description. I always add all the points before I start connecting them. $\endgroup$
    – pgsandstrom
    Apr 12, 2012 at 18:03
  • $\begingroup$ @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. $\endgroup$
    – pgsandstrom
    Apr 12, 2012 at 18:06

2 Answers 2

Reset to default
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This seems to be the best solution. Thank you! $\endgroup$
    – pgsandstrom
    Apr 13, 2012 at 9:10
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Indeed, you are right. Obviously I should cache those values! Thanks! :) $\endgroup$
    – pgsandstrom
    Apr 12, 2012 at 19:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .