2
$\begingroup$

Given $n$ points in $\mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $\mathbf{R}^2$. Prove that each of the additional points must have degree 3, with all three angles being $120^\circ$.

$\endgroup$
  • $\begingroup$ This sounds like homework. What have you tried? $\endgroup$ – adrianN May 8 '13 at 6:56
  • $\begingroup$ It is just an exercise in my course book 'Approximation Algoritms', and I have finished it. $\endgroup$ – Jessie May 8 '13 at 11:13
2
$\begingroup$

Hint 1: If there is a vertex that violate this condition, say a degree 3 vertex, take this vertex out. Now there are three vertices that have lost an edge remaining. Construct the Euclidean ST for these three points and add it back. Obviously your new solution cant be worse than what you head before. Now it remains to check that for 3 arbitrary points in the plane, the Euclidean ST fulfills the angle criterion mentioned in your question.

Hint 2: For a higher degree $v$, replace two consecutive edges $(v,u_1), (v,u_2)$ by the Euclidean ST spanned between $v,u_1,u_2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.