Suppose we have a set S of n line segments, with k connected components. I am trying to solve the problem of finding the minimum number n0 of lines we to add to S to connect the set, with the condition that new lines must share both extremes with any of the lines in S.
My thoughts: the exact solution can be found by exploring all combinations of segments joining points from two different components. This is, however, incredibly expensive for a big set S. I believe we can use some heuristic, like joining first more distant points, but since there is no lower bound to the problem (for example, a set S formed by aligned vertical lines can be connected by a single line) I don't think we have a better option than exploring all combinations.
Is there any theory on the topic I can use? How could approximate solutions be built?