6
$\begingroup$

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.

$\endgroup$
1
  • $\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

1
$\begingroup$

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:


          RectCover
          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.


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

$\endgroup$
1
  • 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

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