connecting cities

2 posts in this topic

Posted · Report post

There are four cities located on the vertices of a square. Your task is to design a network of roads such that (1) every city is connected with every other city, and (2) the total length of the roads is minimized. The roads can intersect each other.

0

Share this post


Link to post
Share on other sites

Posted · Report post

This problem has a surprising solution that becomes apparent when, because of symmetry, we note the road will likely pass through the center of the square. We slice the square through the center with an E-W cut.

Now consider only the south half of the square, and minimize the road length that connects the two lower cities with the square's center. Immediately we see that the triangle they form is suboptimal: the roads from the two lower cities should meet somewhere due south (again by symmetry) of the center, at a point determined by the angle of inclination from due east of the road from the SW city. The road thus makes an inverted Y. The angle that minimizes the overall length of the Y is easily seen to be 30 degrees, and, for a unit square, that length is 2.5/sqrt(3).

The upper half of the road is a mirror image. The minimum road length is thus 5/sqrt(3) ~ 2.887 times the side of the square, and has the shape of two Ys joined at their stems.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.