9
$\begingroup$

The governor of Reniets (a land far, far away!) is known to be very stingy.
He has to build a road which connects all the five cities in the region, which are oddly arranged on the vertices of a regular pentagon (see the picture below).
Building a road is very expensive: the longer it is, the more it costs!
His first idea is to build five roads, each connecting a city to the center of the pentagon, then he realizes that it might not be optimal. In fact, he remembers that, years ago, his friend had to connect four towers, and the solution wasn't trivial!.

enter image description here

How long is the shortest path that connects all the five cities?

Notes:

  • assume that the side is long $1$ km.
  • I currently don't know the solution, I will accept the most convincing answer if no proof is given after some days.
  • If you can generalize the solution to polygons of any number $n$ of sides, I will award a bounty (the amount depends on the quality of the work).
$\endgroup$
  • 4
    $\begingroup$ An NP-Complete problem involving involving a open question. Nice light stuff for a Saturday morning! $\endgroup$ – Bob Jun 13 '15 at 9:02
  • $\begingroup$ @Bob What's the progress to this? Its evening here :) $\endgroup$ – Sharad Gautam Jun 13 '15 at 9:08
  • $\begingroup$ @Bob The actual NP-problem is the generalization to any set of points, not necessarily in a regular pattern. This problem is simply a pentagon, I doubt it is NP-complete; I don't know if it is for regular polygons too, the bounty is for that. Sharad, I've opened a chat room chat.stackexchange.com/rooms/24771/leoll2 for all those who want to ask anything about me. $\endgroup$ – leoll2 Jun 13 '15 at 9:09
  • $\begingroup$ +1 Cool question. How do you come up with stuff like this? $\endgroup$ – JLee Jun 13 '15 at 12:08
  • 1
    $\begingroup$ @JLee Thanks! My original intention was to post the famous square puzzle, but it was already posted by another user, so I decided to add a variation. People seem to appreciate it, I already have few puzzle with similar features ready to be posted in the next days :) $\endgroup$ – leoll2 Jun 13 '15 at 12:20
2
$\begingroup$

Here's the optimal solution for the pentagon:

enter image description here
As the only Steiner tree for this set of five points, it is the only locally minimal solution, hence it must be globally minimal.

For regular hexagons and above, just take the perimeter and remove one edge.

EDIT: Whoops I forgot to calculate the total path length. Brb.

EDIT2: The length of the tree in the pentagon is $${1\over 2}\sqrt{17+7\sqrt{5}+\sqrt{390+174\sqrt{5}}} \approx 3.891 ~\text{km}.$$ For an $n$-gon ($n \ge 6$) the total path length would obviously be $n-1~\text{km}.$

$\endgroup$
  • $\begingroup$ Nice solution! Though, I don't understand the proof; it's not the only Steiner tree for those 5 points, my picture shows another example. Also, can you prove your statement about 6+ edges? $\endgroup$ – leoll2 Jun 13 '15 at 11:47
  • 1
    $\begingroup$ +1 Nice answer, but if I lived in one of the 2 cities on the right, I'd be pissed because I'd need to go way out of my way to travel between them. $\endgroup$ – JLee Jun 13 '15 at 12:07
  • $\begingroup$ @leoll2 Your picture isn't a Steiner tree, because it contains angles smaller than 120°. There's always an easy local optimization when you have one of these angles. And no, I don't know how to prove the statement with n>5 edges, because there's usually more than one possible Steiner tree, for example in an octagon. $\endgroup$ – Anon Jun 13 '15 at 12:29
  • 1
    $\begingroup$ @leoll2 See Theorem 1 in Du, D.Z., Hwang, F.K. & Weng, J.F. Discrete Comput Geom (1987) 2: 65.. $\endgroup$ – noedne May 22 '18 at 21:43
  • 1
    $\begingroup$ It should be written that their angles are 120 degrees. $\endgroup$ – Takahiro Waki Aug 3 '18 at 15:15

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.