Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
What do you mean by “polynomial complexity”? If you know that the problem is NP-hard (although it is not clear to me why), it means that you cannot hope for an algorithm whose time complexity is polynomial unless P=NP. Did you mean that you are looking for an approximation algorithm with approximation ratio bounded by a polynomial? In other words, are you looking for an algorithm which finds a net whose total length is bounded by a polynomial times the total length of the optimal net? – Tsuyoshi Ito Nov 22 '10 at 1:04
Of course, I'm looking for an approximation algorithm which computional complexity is polynomial. It's NP because it's special case of Steiner tree problem which is NP but none of the (known to me) aproaches to the Steiner tree problem cannot be applied to this problem. – Łukasz Sowa Nov 22 '10 at 18:17
I fail to see why this problem is a special case of the Steiner tree problem. It looks to me that the two problems ask similar but different things. – Tsuyoshi Ito Nov 23 '10 at 13:50
Being in NP and being NP-hard are two very different notions, and a special case of NP-hard problem is not necessarily NP-hard. – Tsuyoshi Ito Nov 23 '10 at 13:50
By the way, it is not 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.” – Tsuyoshi Ito Nov 23 '10 at 13:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.