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 instances of any specified shape - the covering shape could be circle, square, rectangle and so forth - such that the total area of the covering shapes is minimum and with no constraint on the sizes of the instances of the covering shape being used.

For example, one uses N squares to cover C such that the sum of the areas of these squares is least but these N squares need not be equal among themselves.

Other optimizations such as minimizing the sum of the perimeters of the covering shapes 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$ – Gerhard Paseman Jul 31 at 8:51

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$ – Nandakumar R Jul 31 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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