CODEWITHSUNDEEP
algorithmmathgeometry
Andrew Tomazos
Andrew Tomazos

Reputation: 68588

Algorithm for connecting set of points?

Suppose we are given a set of N points (xi,yi) in the real plane.

We want to connect them with any number of lines, such that for every pair of points A, B - there is a path from A to B (possibly indirectly through another point) - and the total length of the lines is minimal.

For example, suppose these are towns in a desert and we are constructing a road network. We want to use the minimum amount of materials to construct the roads but still have every town reachable by road.

For N = 2 the solution is of course simply a line segment between the two points:

+------------------+

For N = 3, suppose the points are colinear, then the solution is again one line segment:

+------+-----------+

For N = 3, suppose the points would make the vertexes of an equilateral triangle, then we would add a point in the center and then construct three line segments connecting the new central point to each of the three points:

         +
         |
         |
        / \
       /   \
      /     \
     +       +

I'm sure the problem and its solution should be well-studied. Does the problem and/or algorithm have a name?

Upvotes: 2

Views: 2231

Answers (1)

High Performance Mark
High Performance Mark

Reputation: 78306

Well, never one to pass up easy rep ...

Consider the Steiner tree problem which seems to describe your problem more closely than the minimal spanning tree. To quote from that article:

The difference between the Steiner tree problem and the minimum spanning tree problem is that, in the Steiner tree problem, extra intermediate vertices and edges may be added to the graph in order to reduce the length of the spanning tree.

Upvotes: 2

Related Questions