10
$\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).
Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ An NP-Complete problem involving involving a open question. Nice light stuff for a Saturday morning! $\endgroup$
    – Bob
    Commented Jun 13, 2015 at 9:02
  • $\begingroup$ @Bob What's the progress to this? Its evening here :) $\endgroup$
    – Sharad Gautam
    Commented Jun 13, 2015 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
    Commented Jun 13, 2015 at 9:09
  • $\begingroup$ +1 Cool question. How do you come up with stuff like this? $\endgroup$
    – JLee
    Commented Jun 13, 2015 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
    Commented Jun 13, 2015 at 12:20

1 Answer 1

Reset to default
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}.$

Improve this answer
$\endgroup$
6
  • $\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
    Commented Jun 13, 2015 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
    Commented Jun 13, 2015 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
    Commented Jun 13, 2015 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
    Commented May 22, 2018 at 21:43
  • 1
    $\begingroup$ It should be written that their angles are 120 degrees. $\endgroup$
    – Takahiro Waki
    Commented Aug 3, 2018 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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