Welcome to MathOverflow

Question

2

Given n affinely independent points in n-1 dimensional Euclidean space, how is the minimum Steiner tree constructed? Or assuming that the topology of the Steiner tree is given, is there an easy way to find the minimum edge lengths? I want a closed form algorithm if possible, otherwise an iterative solution that converges to the right answer with some kind of error bound would also be useful.

edited Oct 21 2009 at 1:18

Anton Geraschenko♦♦
13.7k●3●48●108

asked Oct 20 2009 at 21:47

asdf
21●1

what's the connection to symplectic geometry? – jc Oct 20 2009 at 23:42

Greg Kuperberg · Answer 1 · 2009-11-04 02:26:59Z UTC

Certainly if you're given the combinatorial type of the Steiner tree, you can efficiently find its position. The length of each edge is a convex function of the positions of the internal vertices of the tree, so their sum is too. So you can approximate the minimum numerically with convex programming.

On the other hand, this book says that finding approximate solutions to the Euclidean Steiner problem is NP-hard. So the part that is NP-hard must be finding the combinatorial type of the tree. Naturally, many NP-hard problems have a lore of heuristic methods, and the same book is a survey of these methods in the case of the Steiner problem.

Note that the affine independence condition doesn't change very much since the points could be close to lying in a hyperplane.

A final comment which is slightly off topic. Some years ago, my mother found an example where the Steiner tree in R³ of a finite set of points on the unit sphere S² is knotted.

asdf · Answer 2 · 2009-10-21 00:02:22Z UTC

0

Sorry I'm too dense to figure out how to use this website so I'm apparently posting this response as an answer -- the n points define vertices of a simplex in the n-1 dimensional space, so when I saw the tool-tip suggestion "symplectic-geometry" when I typed "geometry" I added it too; if this has nothing to do with symplectic geometry then a mod can delete the tag.

answered Oct 21 2009 at 0:02

asdf
39●1

	You should be able to add a new comment to your question by clicking the "add comment" link at the bottom left (of the question). I've removed the tag [symplectic-geometry]. You can delete this answer by clicking the "delete" link, which should be in gray, just above this comment, on the left side, next to "link", "edit", and "flag". – Anton Geraschenko♦ Oct 21 2009 at 1:20
	Ohhhh, I see the problem. You're not a registered user, so the only way the site can keep track of you is with a cookie. After you asked the question, you must have deleted the cookie, so the site didn't recognize you as the owner of the question. The easiest way to fix this is to register an account, and then ask me to merge these two accounts into the registered account (which you can do here: mathoverflow.net/questions/24). – Anton Geraschenko♦ Oct 21 2009 at 1:23

High dimensional Steiner tree

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.