Calculating Minimum Number of Radio Towers for Complete 100 Mile Coverage

[Loren Booda]

A radio tower broadcasts within a 50 mile radius. At a minimum, how many such towers are needed to completely cover a 100 mile radius?

 

[Loren Booda]

To simplify the problem geometrically:

Consider a disk with a 50 centimeter radius. At a minimum, how many such disks are needed to completely cover a disk with a 100 centimeter radius?

 

[klackity]

The area of the larger disk is four times the area of the smaller disk. So this is a lower bound. But this is not achievable. We need to look for a tighter lower bound.

We know we need to cover the boundary of the disk. The length of the boundary of the large disk is 2*pi*r where r is the radius of the large disk.

Now consider a small circle intersected with the large circle such that the intersection points are diametrically opposite points of the small circle. Call these points A and B. These intersection points, along with the center C of the large circle, provide us with enough information to deduce the maximal length of a large-disk-boundary-segment that can be covered by a single small disk.

The triangle formed by A,B, and C is equilateral, where sides CA and CB are both length r due to being radii of the large circle, and side AB is of length r due to being the diameter of the small circle. Thus the angle (in radians) formed by CA and CB is pi/3.

Thus a single small circle can only cover r*pi/3 of the whole boundary of the large circle. So our lower bound is improved to six. Or rather, it can be improved to seven, because six is only minimally sufficient to cover the boundary, and necessarily cannot cover the interior if it covers the boundary.

An upper bound is 12. So, it lies somewhere between 7 and 12, inclusive. Uh.. that's all I've got.

 

[Ben Niehoff]

The answer is 7. Think of them as regular hexagons rather than circles, and it should be obvious.

 

[Loren Booda]

Permit me to restate the problem:

"At least how many disks with equal radii completely cover one disk with radius twice theirs?"

First of all, we are dealing with disks -- i.e., the region enclosed by a circle in its plane. Small squares would be no problem -- only nine needed.

Secondly, if you use a compass as an aid you will find it quite difficult to cover all of the spaces left between the small disks.

Finally, I believe that up to 31 small disks may be needed to cover the large disk. Covering the large disk often demands that more than one small disk overlap each other.

 

[Loren Booda]

I am sorry that this problem turns out to be unremarkable.

 

[klackity]

Haha, Ben Niehoff has it right.

As I correctly pointed out, it takes EXACTLY 6 of the smaller disks to cover the boundary of the large disk. Ben Niehoff, however, realized that this implies that hexagons inscribed into the smaller circles still cover the boundary of the larger circle. (You can work this out with a bit of geometry). Then, because of a special property of hexagons, this implies that it only takes one additional small hexagon in the center to cover the entire disk.

If we then consider the circles which circumscribe those hexagons, we see that they have exactly the properties required. Look at this illustration:

You can see that the red circle has radius exactly twice that of the blue circles.

 

[DaveC426913]

Eloquent answer klackity.

 

[Loren Booda]

Great visuals, klackity. I appreciate your setting me straight. Yours may well be the most efficient example.