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$

1 Answer 1

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$
4
  • $\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$ Nov 29, 2014 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, 2014 at 21:56
  • $\begingroup$ At the moment this paper can be accessed here. $\endgroup$
    – flawr
    Oct 31, 2015 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, 2016 at 21:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .