Given a convex 2D region $C$ and a positive integer $N$. We need to cover $C$ with $N$ rectangles such that the sum of the areas of the $N$ rectangles is the least – no further constraints on the dimensions of the $N$ covering rectangles. Then,

  1. Are we guaranteed to get an 'optimal $N$-rectangle cover' of $C$ if we insist that the orientations (direction of the length) of all $N$ rectangles ought to be the same? (Note: If the answer is "yes", finding algorithms for 'optimal $N$-rectangle cover of $C$' would become easier)

  2. If answer to (1) is "yes", one can ask: for the same $C$, if $N$ is varied, can the orientations of the 'optimal rectangle covers of C' always be chosen for every $N$ from a very small set? One guesses one can choose from only 2 possible orientations and get an optimal rectangle cover of $C$ for any $N$.

  3. What about higher dimensional analogs to this question?

Note: Not sure if the following broader class of problems has been explored...

Covering a given convex region $C$ with a specified number $N$ of mutually similar instances of any specified shape - the 'covering units' could be $N$ circles of possibly varying sizes or $N$ squares of not necessarily same side ... - such that the total area of the covering units is minimum and with no constraint on the sizes of the instances of the covering shape being used.

Guess: In the case of covering $C$ with $N$ rectangles, the best layout (one which minimizes the total area of the $N$ covering units) is always such that the $N$ covering units have no overlaps among themselves. Indeed, if $C$ could be non-convex, the covering units in the best layout may overlap.

Note: This guess is not applicable if the covering unit shape 's' is a circle or a convex polygon with large number of sides. Even if we consider covering a convex shape C with N equilateral triangles, it appears that at least for some C and N, the covering equilateral triangles have to necessarily overlap if their total area is to be least.

Note: Other optimizations such as minimizing the sum of the perimeters of the covering units also could be thought about.

  • $\begingroup$ Consider a regular hexagon and N=3. Generalize. Gerhard "Need To Cover Edge Cases" Paseman, 2019.07.31. $\endgroup$ Commented Jul 31, 2019 at 8:51

1 Answer 1


OP: "Are the orientations (direction of the length) of all $N$ rectangles necessarily the same?"

This $N=2$ example covering a triangle suggests the answer is No:

          The two pink $5 \times 3$ triangles are congruent.
If we let $x$ be the length of the blue horizontal arrow, then I calculate the (pink) wasted area as $A=\frac{1}{2} \left( \frac{3}{5} x^2 + \frac{3}{5} (10-x)^2 \right)$, whose minimum is achieved at $x=5$ as illustrated.

Added. As the OP remarks, my example only shows that "necessarily" is too strong.

Another example, $N=2$ covering of a trapezoid. But flawed in that one could achieve the same waste with just one rectangle.

          Trapezoid has base $8$ and top $7$.
So perhaps optimality should exclude two rectangles sharing a whole edge of each.

  • 1
    $\begingroup$ A cover of the same quality can be got also by a 3X10 and a 3X5 rectangle both with the same orientation. So, I have restated the question statement removing the "necessarily". $\endgroup$ Commented Jul 31, 2019 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.