5
$\begingroup$

Consider a set of $n$ points in the plane. Among all the connected graphs (trees) $T$ in the plane that have these $n$ points among their vertices, I am looking to find one such that the sum of its edge lengths is minimum. Note that this question is different from Minimum Spanning Tree as we allow $T$ to have vertices other than the given $n$ points. For example, if $n=3$, there are 2 possibilities: Let $A,B,C$ be the three given points. If one of the angles in the triangle $ABC$, say $ABC$ is bigger than $120^\circ$ then AB+BC is the minimizing tree. If all the angles are less than $120^\circ$, let $P$ be the point within the triangle $ABC$ such that the angles $APB$, $BPC$, $CPA$ are all $120^\circ$. Then the tree $T$ with the set of vertices $A,B,C,P$ and edges $AP,BP,CP$ is the length minimizing one.

Is this problem worked out before?

$\endgroup$

1 Answer 1

7
$\begingroup$

This is the so-called Steiner Tree Problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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