Writing Project 13:

Radio station problem

First use the internet to find out what the convex hull of points in the plane is. Then consider the following problem:

In a certain county there are 12 villages with coordinates (-3,2), (2,3.5), (4,1), (0,1), (-1,-2), (-3,-2), (6,-1), (1,3), (3,0), (4,-1.5), (-2,4), (-2,-3.5). The task is to find a location for a radio station. The quantity that measures the quality of such a location is the maximum distance from the station to the villages, i.e. the radius of a circle with the radio station as center, that covers all villages.

Why can we exclude six of the villages in the consideration.

Find a decent location for the radio station, and show that no solution can be more than 20% better (with respect to the above mentioned measure) than yours.

Erich Prisner, August 2003