Edit made on December 03, 2009 by RiderOfGiraffes at 22:18:57
Deleted text in red
/
Inserted text in green
WW
HEADERS_END
[[[> IMG:City1.png ]]] The diagram below at right represents the roads of a city which
are either parallel or perpendicular to each other like the Isle of Manhattan in
New York or parts of Edinburgh. The red circles represent newspaper sellers. The
problem is to find the place to site a depot so that the total distance the newspaper
vendors have to travel (along the streets) to the depot is as small as possible.
IMG:City1.png
There is a convenient method of finding the position by voting !!!
Firstly, place a green East-West line on the map of the city on which the depot will be placed and ask the the vendors to vote whether it should be moved North/South. Any move is performed if it has a majority of vendors in favour. Similarly, a blue North-South line is placed on the map and voting is undertaking on its position. When no move North, South, East or West gains a favorable majority of the newspaper sellers, the depot is placed at the intersection of the green and blue lines.
The diagram below shows the position of the depot that minimises the total distance.
IMG:City3.png
The problem above conveniently has an odd number of newspaper sellers. What difference would it make if there were an even number?
Can you justify why this method finds the optimum position of the depot?