A finite collection of disks covers a subset X of the plane. Show that we can find a pairwise disjoint subcollection S, such that X ⊆ ∪{3D : D ∈ S}, where 3D denotes the disk with the same center as D and 3 times the radius.
Solution
Trivial.
The key observation is that if disk D has larger radius than any disk intersecting it, then 3D covers D and any disks intersecting it.
So take D1 to be the largest disk. Remove D1 and those intersecting it. Now take D2 to be the largest disk remaining. And so on.
© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998