1
$\begingroup$

As it happens, I am currently frantically writing loads and loads of words for NaNoWriMo. One of the chapters I will be writing tonight essentially has the characters approximate a Steiner tree on seven points with rope. In various places, I can find graphics of Steiner trees on three points, four points at the corners of a rectangle, six points (not as the vertices of a regular hexagon), and a couple others, but there seems to be no graphic online for seven points. As I will be writing all day, I don't have time to code up a program to generate these graphics.

Hence, I was hoping that someone else could 1) generate such a graphic so that I know what it looks like or 2) direct me to a program that I can use to generate such a graphic. What would the Steiner tree for seven points look like?

$\endgroup$
2
$\begingroup$

This is going to be a disappointing answer I fear.

There is a paper called "Steiner minimal trees for regular polygons" by Du, Hwang and Weng in the journal Discrete & Computational Geometry (1987), Volume 2, Issue 1.

Unfortunately I don't have access to the paper, but the abstract claims that they show that for $7\leq n\leq 12$, a Steiner tree for $n$ points forming the corners of a regular $n$-gon is obtained by deleting one side of the $n$-gon.

Finding a Steiner tree for all other $n$ was already solved way back in 1934. So while I don't know why the range $7\leq n\leq 12$ is so special, proving that the above is a Steiner tree for $n=7$ is evidently nontrivial somehow.

$\endgroup$
  • $\begingroup$ Darn! I was expecting something much more interesting. Maybe I'll make it an irregular heptagon. Nonetheless, thank you for answering my question! :) $\endgroup$ – El'endia Starman Nov 29 '14 at 21:39
  • $\begingroup$ No problem. It's also unclear if the Steiner tree in the $n=7$ case is unique. Maybe there is a more interesting one! $\endgroup$ – Casteels Nov 29 '14 at 21:56
  • $\begingroup$ At the moment this paper can be accessed here. $\endgroup$ – flawr Oct 31 '15 at 0:12
  • $\begingroup$ the range 7≤n≤12 so special ? merely because the angles matter a lot to localize the Steiner points if any. With regular figures, the main problem is a competition between ex-aequo solutions. There are heuristics to limit the bias of the decimal approximation and unnecessary competitions $\endgroup$ – user354674 Aug 16 '16 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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