TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Tuesday, July 30, 2019

Covering With Rectangles

Note: The question statements have been upgraded following a comment from Prof. Joseph O'Rourke

Given a convex 2D region C and a positive integer N. We need to cover C with N rectangles so that the sum of the areas of the N rectangles is the least – no further constraints on the dimensions of the 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 for any given C, one can choose from only 2 possible orientations and get an optimal rectangle cover of C for any N.

3. If both above questions have a "yes" answer, do the above properties hold even if we replace 'rectangles' with 'ellipses' or with any other convex shape with a center of symmetry? And yes, are there higher dimensional analogs?
------------------
Note: Similar questions can also be asked about N rectangles put inside C such that they together cover the maximum portion of C. Is the best such configuration of N rectangles inside C always one where the rectangles do not overlap?
The answer for this question appears to be that insisting the rectangles to be of same orientation could lead to a suboptimal solution. See this picture:

For the given right triangle, with N=2, if the inner rectangles have to be of same orientation, at most only 2/3 of the right triangle appears coverable. However, as in the second configuration with 2 red rectangles which overlap and are oriented differently, we have a coverage of 3/4 which can even be further improved.
------------------
Update (August 3rd 2019)
On question 3 above: Extending of the claim on rectangles to regions with central symmetry has problems. Indeed, it is easily shown to be so for rhombuses. See picture below. A pentagon shown covered by 2 rhombuses (black and blue) which are not aligned in the same direction. No other pair of rhombuses appears to give a better coverage.

However, the pentagon can be covered with 2 non-overlapping parallelograms parallelly aligned to each other and with the same combined areas as the blue and black rhombuses shown above.

0 Comments:

Post a Comment

<< Home