Monday, July 06, 2020

Covering with Rectangles etc - 2

Here, we add a bit to this earlier post:
https://nandacumar.blogspot.com/2019/07/covering-with-rectangles.html

Basic question: To cover a given convex shape C with N rectangles (no further constraints on the dimensions of the rectangles; they could be different) such that the sum of the areas of the N rectangles is the least.

Variant: To cover C with N instances of the same shape - the sizes of the 'covering units' could be different; they just need to be similar to each other - such that the covering units have the least area sum. Eg: covering C with squares, equilateral triangles or triangles all similar to one another.

Guess: In both above questions, the best layout is always such that the N covering units have no overlaps among themselves. If C could be non-convex, they may overlap.

Remarks on this Guess: When the covering units are all circles or mutually similar instances of a convex polygonal shape with large number of sides - then, the units necessarily overlap so the above guess does not hold for those shapes. But it seems plausible when the covering is done with a set of N mutually similar triangles or with N rectangles (which need not be similar among themselves)

However, here is a Partial Counter-example:
Consider C to be as shown in picture in red (its angles are 90, 120, 90 and 60 degrees). Take N=3 and the covering shape to be 'equilateral triangle'. It seems the cover of C with 3 equilateral triangles of least total area of units necessarily has an overlap - two such arrangements are shown in pic and that any covering layout with 3 non-overlapping equilateral triangles will have greater combined area of covering units..


So, the guess might have to be restricted only to covering with rectangles. And as usual, onecasks, what about 3D?
Note 1: In the post linked at the top, we observed that if the problem is that of filling the interior of C with N rectangles none of which has any point outside C, then, the coverage of the interior can be improved by allowing the units to overlap - although at the cost of an increased sum of the areas of units.

Note 2: Naturally, questions on finding algos which (1) cover C optimally with N suitable rectangles and (2) fill as much of the interior of C with N suitable rectangles could be asked. One feels algorithms of class (1) are easier to find.

No comments:

Post a Comment