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: 1. Every two points are connected with shortest edge. 2. 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 aproaches 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 aproach is rather naive: connect every two points with an edge and then merge the edges that are overlapping.