# On covering convex 2D regions with rectangles

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.

• Consider a regular hexagon and N=3. Generalize. Gerhard "Need To Cover Edge Cases" Paseman, 2019.07.31. – Gerhard Paseman Jul 31 '19 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.

• 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". – Nandakumar R Jul 31 '19 at 16:16