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$
7
$\begingroup$

This is the so-called Steiner Tree Problem.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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