I'm looking for an algorithm to solve this problem:
Given set of n points on 2D euclidean space, create a net of rectilinear edges, so that:
- Every two points are connected with shortest edge, and
- sum of all edges is minimal (minimized).
That's clearly a NP-hard problem and it's similar to Steiner tree problem, but I can't use any of the common approaches because of constraint $1$. Moreover, in my case, every algorithm to solve that problem is feasible as long as it has polynomial complexity - the function of the objective is here the key.
Any good ideas how to solve this? My current approach is rather naïve: connect every two points with an edge and then merge the edges that are overlapping.