Covering convex sets by smaller homothetic sets

Definition:

We say that \(F'\) is a smaller homothetic set of \(F\) if \(F'\) is the image of \(F\) by a homothety \(h\) of some center \(O\) and positive ratio \(k<1\).

To cover a circle at least three smaller homothetic circles are needed!

This can be observed and experimented with in the figure below, on which every red point can be moved.

The black circle is the original circle that we wish to cover with the circles \(c1\) (green), \(c2\) (blue) and \(c3\) (red). The points \(k1\), \(k2\) and \(k3\) represent the ratios of the homotheties and \(O1\), \(O2\), \(O3\) their centers. Ignoring the circle \(c3\), move \(k1\) and \(k2\) trying to cover the circle with only two smaller circles. (Note that, by the definition of the problem, the homothety ratio must be smaller than one.) Are you unable to do it? Then try changing the positions of the homothety centers... In fact, two circles are not enough!

Click the button to show the third homothetic circle and you will then be a able to complete the desired covering.

(The following applets were produced with the help of JavaSketchpad)

Sorry, this page requires a Java-compatible web browser.


Click the third button to know why are two smaller homothetic circles not enough to cover the circle. Point \(A\) (or its antipodal point) cannot be covered by the two circles since

\(\overline{AC1}>\overline{AC} = \) radius of \(c\) and \(\overline{AC2}>\overline{AC} = \) radius of \(c\)

and, since the ratios of the homotheties \(h1\) and \(h2\) are smaller than one, the smaller homothetic circles \(c1\) and \(c2\) have radius always smaller than the radius of \(c\).

To cover a parallelogram we need at least four smaller homothetic parallelograms!

This can be observed and experimented with in the figure below, on which every red point can be moved.

The black parallelogram is the original one that we intend to cover. Each of the other colored parallelograms is an image of it by a homothety of ration smaller than one. The points \(k1\), \(k2\), \(k3\) and \(k4\) represent the ratios of the homotheties and \(O1\), \(O2\), \(O3\) and \(O4\) are the homothety centers. Without seeing the fourth parallelogram, move \(k1,\) \(k2\) and \(k3\) to see if you can cover the parallelogram with only three smaller homothetic parallelograms. Can't do it? Then try to also adjust the homothety centers... Once again, the reality is that three parallelograms are not enough! Click the button to show the fourth parallelogram: then you will be able to obtain the desired covering.

In fact, since the sides of the homothetic parallelograms are parallel to the sides of the original one and since the ratio of the homotheties is less than one, each smaller homothetic parallelogram can cover at most one vertex of the original; we need therefore at least one for each vertex that is, four smaller homothetic parallelograms, to obtain the desired covering.

Similarly, one can observe that the number of homothetic smaller sets needed to cover a parallelepiped is eight. And if we generalize to an \(n\)-dimensional space, we still have that an \(n\)-dimensional parallelepiped can be covered by \(2^{n}\) smaller homothetic parallelepipeds and not by less.

Any bounded convex set in the plane that is not a parallelogram can be covered by three smaller homothetic sets of itself.

You can explore this result in the sketch below, changing the original figure, in black, taking in consideration that the figure must be convex (and should also not be a parallelogram since in that case four homotheties would be needed) and moving the centers of the homotheties and changing the ratios of the homotheties, while keeping them smaller than one so that the homothetic sets are smaller than the original.

Sorry, this page requires a Java-compatible web browser.

Attempts have been made to generalize this result to higher dimensions resulting in the following conjecture:

Hadwiger's conjecture (1957):

Given a bounded \(n\)-dimensional convex body that is not a parallelepiped, the least number of smaller homothetic sets to it with which it can be covered is smaller than \(2^{n}\); this number is \(2^{n}\) only in the case of the \(n\)-dimensional parallelepiped.

However, this conjecture has not yet been proved or disproved, not even for the \(n=3\) case.

Some weaker results have been attained, though. Let \(b(F)\) be the least number of smaller homothetic sets to \(F\) with which \(F\) can be covered. The following upper bounds for certain special sets were proven:

There is also a lower bound for this number: