Writing Project 38:

Placing Restaurants

a) In quadratic city (with side lengths 4km) there are two fast food restaurants: Red Burger, which has already two restaurants opened with coordinates (1,2) and (3,2), and Blue Burger with only one location at (2,3) so far. The assumption is that everybody goes to the nearest fast food restaurant, no matter whether it is red or blue. So each point in the city is colored according to the color of its nearest restaurant.
Click anywhere in the square city to place a second blue restaurant. Where should it be located to maximize the total blue area, the area of the city closest to a Blue Burger restaurant. Give some reason to your answer, and also compute the resulting blue and red areas.

b) If that was too easy, try the following variant with three existing Red Burger restaurants at coordinates (1,1), (2,3), and (3,1), and with two existing Blue Burger restaurants at ((1,3) and (2,2). Again the question is where to place the third Blue Burger restaurant. This time, trying to maximizing the blue area is too difficult, but you should make a choice and compute the resulting blue and red areas. Maybe you can also justify your choice to some extend?

c) The resulting geometrical patterns are called "Voronoi diagrams", see also this page for a variant. You could also write a little about Voronoi diagrams in general.

Erich Prisner, August 2003