Minimum rectilinear net I'm looking for an approximate 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.
 A: One approach would be to use minimum spanning trees in $L^1$ rather than Steiner trees. As you specify a rectilinear net, either you already have a grid or you can compute one in polynomial time from the vertices.
You have a conflict with a Euclidean space ($L^2$ norm) and a rectilinear net ($L^1$ norm) so it is unclear what you mean by shortest in "every two points are connected with shortest edge". MST algorithms will satisfy both constraints in the norm you choose for calculating the edge weight. If you choose $L^1$ the edges will be rectilinear.
Kruskal's algorithm is a straightforward algorithm that will let you see if a MST is a suitable approximation for your problem.
Other, more optimal algorithms exist, including Chazelle's practically linear algorithm, randomized algorithms such as Karger, Klein and Tarjan's and the provably optimal decsion tree algorithm from Pettie and Ramachandran.
As your graph is dense (every edge in the rectilinear grid is possible so you have many more edges than vertices), there is a linear time algorithm from Fredman and Tarjan (Chazelle's is also linear on dense graphs), but I would start with Kruskal.
