Staying connected, cheaply

Geometry Level 2

Mr. Dlanod, a notorious developer, plans to build eight hotels in the wilderness (complete with casinos and golf courses), at the points shown in the diagram. A network of roads needs to be built so that any hotel is connected to any other, but the budget allows for at most 13 km of roads. (We are allowed to introduce crossroads and intersections, of course.)

Can the task be accomplished?

Bonus: What is the minimum total length of such a network of roads?

Yes No It's an open problem

2 solutions

Mark Hennings
Nov 14, 2018

Connect the left-hand four hotels with a Steiner system (each angle at the intersections is $120^\circ$ ), and do the same with the right-hand four hotels. Then join up the two sets of four hotels.

Each angled line in a Steiner system has length $\tfrac{2}{\sqrt{3}}$ , while the central horizontal lines have length $2 - \tfrac{2}{\sqrt{3}}$ . Thus each Steiner system has length $4 \times \tfrac{2}{\sqrt{3}} + 2 - \tfrac{2}{\sqrt{3}} = 2\sqrt{3} + 2$ , and so the whole network has length $2(2\sqrt{3}+2) + 2 = 4\sqrt{3} + 6 = 12.928...$ .

It is possible to join the hotels cheaply as required.

Since the Steiner systems are the shortest ways of joining each of the two sets of four hotels together, I suspect that the distance $4\sqrt{3}+6$ is minimal.

How do we know that "the Steiner systems are the shortest ways"? What would you do if "Dlanod" the megalomaniac would decide to build 22 hotels, for example, in a 2 x 11 pattern? Or what about a 7 x 7 pattern? Lots of fun questions to ponder: What about "hotels in the sky" and a 3D-pattern?

Otto Bretscher - 2 years, 6 months ago

I point you in this direction where the principles of Steiner systems for four vertices are set out.

As you say, once there are more vertices, the problems get very complex. For example, Steiner systems for the vertices of regular polygons become trivial (the edges of the polygon minus one) for pretty small polygons - it has been shown that we get trivial Steiner systems for regular heptagons and above. Is it not the case that the general problem of finding a minimal Steiner tree on a graph is NP-hard? You will note that I merely said that I suspected that my given pattern was optimal.

The geometry of minimal distance/minimal surface area problems is generally speaking pretty complex - there are some soap bubble patterns on wire frames (which represent minimal surface area, of course) that have not been explained yet.

Mark Hennings - 2 years, 6 months ago

Interesting!

Otto Bretscher - 2 years, 6 months ago

Thanks for your answer, it is really elegant! For those looking for more informations, this problem is actually know as the Steiner Tree problem . It would be interesting to add an arbitrary number of points in the network and try to solve it, there might be a more optimal solution than yours :)

Thomas Reynaud - 2 years, 6 months ago

If you follow the further adventures of Dlanod, (Otto has posted three), you will eventually find a link to a paper which answers your question.

Mark Hennings - 2 years, 6 months ago

It turns out that for an $n \times 2$ "ladder", where $n$ is even, this simple type of Steiner tree is optimal. The odd case is much more difficult to analyse, as we have discussed in some additional problems.

Here and here .

Otto Bretscher - 2 years, 6 months ago

Bees are smart insects!

Carlo Wood - 2 years, 6 months ago

Ak Gh
Nov 20, 2018

As @Mark Hennings , Steiner systems are the layouts that have the minimal distance. The proof can be shown mathematically, but it's interesting to see how nature minimizes it too. See this example of a soap film that has to connect 4 pins. It follows the Stenier system.

Indeed, since the soap film is achieving the minimum surface area (and the gap between the two plates is constant), this experiment will certainly yield Steiner systems.

Mark Hennings - 2 years, 6 months ago

As a country man of the great Jakob Steiner, allow me a small remark on terminology: These are Steiner trees; Steiner systems are somethings else altogether, a combinatorial concept. Steiner did important work in many fields.

Otto Bretscher - 2 years, 6 months ago

Can you give a link to the mathematical proof of a 3 pin or even a 4 pin network as I don't seem to find any for equally spaced pins when I searched online.

Tausif Hossain - 2 years, 6 months ago

If you follow the further adventures of Dlanod, Otto has written four so far, in the third one I give a link to just such a paper.

Mark Hennings - 2 years, 6 months ago

@Tausif Hossain Check out if these can help you:

https://thatsmaths.com/2015/01/29/the-steiner-minimal-tree/

https://www.jstor.org/stable/27961673?seq=1#page scan tab_contents

AK GH - 2 years, 6 months ago

Thank you for the link!

Tausif Hossain - 2 years, 6 months ago

Example of the soap film is actually the mathematical proof i.e. a soap bubble is just the opposite of it, being the largest surface area passing through all of the eight corners of a cube (if you will to transport the problem into three dimension, as one of the commentators suggested "hotels in the sky"). Thence, if you want to find the smallest surface area passing through all corners, all you have to do is get the homothetic transformation of the spheric bubble over the corners ! A bubble inflated to positive (blow); you first deflate it to zero - then further suck it to negative (complete collapse to oblivion) ... You can try it with a balloon; I did. By the way, isn't that cute how it shows similarity to Big Bang ? The thing goes all the way deep deep deep... into quantum physics and mechanics.

F Uğurel - 2 years, 6 months ago

A caveat is in order, though: The soap film finds a local minimum only, not necessarily the surface corresponding to the Steiner minimal tree.

Otto Bretscher - 2 years, 6 months ago

Just one point, nature does not follow us, we follow and discover, just a way to put

San Seng - 2 years, 6 months ago

Staying connected, cheaply

2 solutions

0 pending reports