1
$\begingroup$

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, and
  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 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.

  • 0
    By the way, it is $n$ot at all clear from the question that you are looking for an approximation algorithm. I appreciate if you can clarify the question before saying “of course.”2010-11-23

0 Answers 0