[Solved]: Euclidean Steiner Tree Question in Approximation Algorithms

Problem Detail: 

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$.

Asked By : Jessie

Answered By : A.Schulz

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11880

 Ask a Question

 Download Related Notes/Documents