Length minimizing graphs between a finite set of points
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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?
co.combinatorics graph-theory extremal-graph-theory
asked 3 hours ago
Mohammad F. Tehrani
2,9531655
add a comment |Â
up vote
2
down vote
favorite
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?
co.combinatorics graph-theory extremal-graph-theory
asked 3 hours ago
Mohammad F. Tehrani
2,9531655
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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?
co.combinatorics graph-theory extremal-graph-theory
asked 3 hours ago
Mohammad F. Tehrani
2,9531655
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?
co.combinatorics graph-theory extremal-graph-theory
co.combinatorics graph-theory extremal-graph-theory
asked 3 hours ago
Mohammad F. Tehrani
2,9531655
asked 3 hours ago
Mohammad F. Tehrani
2,9531655
asked 3 hours ago
Mohammad F. Tehrani
2,9531655
asked 3 hours ago
Mohammad F. Tehrani
2,9531655
asked 3 hours ago
Mohammad F. Tehrani
2,9531655
2,9531655
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
4
down vote
accepted
This is the so-called Steiner Tree Problem.
answered 2 hours ago
Igor Rivin
78.6k8112305
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
This is the so-called Steiner Tree Problem.
answered 2 hours ago
Igor Rivin
78.6k8112305
add a comment |Â
up vote
4
down vote
accepted
This is the so-called Steiner Tree Problem.
answered 2 hours ago
Igor Rivin
78.6k8112305
add a comment |Â
up vote
4
down vote
accepted
up vote
4
down vote
accepted
This is the so-called Steiner Tree Problem.
answered 2 hours ago
Igor Rivin
78.6k8112305
This is the so-called Steiner Tree Problem.
answered 2 hours ago
Igor Rivin
78.6k8112305
answered 2 hours ago
Igor Rivin
78.6k8112305
answered 2 hours ago
Igor Rivin
78.6k8112305
answered 2 hours ago
Igor Rivin
78.6k8112305
78.6k8112305
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f314645%2flength-minimizing-graphs-between-a-finite-set-of-points%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password