Given $n$ points in $\mathbb{R}^2$, how can I find a set of lines (length, starting point and direction) $L$ such that all points are connected by these lines and the sum of lengths of the lines is minimal?
I tried using graph techniques but it forces me to define infinitely many vertices.
Is there an anlytic approach to solve this problem?
EDIT
It is similar to "The Traveling Salesman" problem only that the lines are not obligated to start and/or end in one of the $n$ points
On
I assume you want every point to be reachable, along a set of connected lines, from any other point. If we consider this as a weighed graph with the nodes being your points and the edges being the lines between them (with their weight being the Euclidean distance), it is clear that any cycles we have can be eliminated without affecting this property. So your criteria is equivalent to finding a minimum spanning tree for this graph.
One simple method to find such a tree is Prim’s algorithm.
First, compute the distance between every set of two points. Then, beginning at an arbitrary point, iteratively choose the shortest line connected to this point that connects to a point that is not yet connected to. When all points are connected, we are done and are guaranteed a minimum spanning tree. The set of edges in this tree will satisfy your criteria.
Other more sophisticated algorithms exist that have better time or space complexity properties.
This is the (geometric) Euclidean Steiner Tree problem. (Also described in the Compendium of NP Optimization Problems.) For arbitrary $n$, the Euclidean Steiner Tree problem is NP-hard. There is a polynomial-time approximation scheme described in Arora et al., with most of the discussion in section 3.1.