TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Wednesday, September 05, 2018

Doubts on Covering

Consider trying to cover the largest scaled copy of a region C with n instances of a fixed tile T (iow, we were asking how big a circle or square or... (C) could be covered with n copies of an equilateral triangle of unit side or unit square square or unit circle .... (T) (see Erich's Packing Center for several families of such questions: (https://www2.stetson.edu/~efriedma/packing.html)

Question 1: In the best covering layout for a given C with n T's, consider regions where where more than one T unit overlap. The observation is that if T is non-convex, the best layout could have regions where an arbitrarily large number of T units overlap (see below).
However, for the case when T is convex, no known best covering layout (as seen at say, Erich's Packing Center), seems to have regions where more than 3 unit Ts overlap. [Eg: see this page of covering largest possible squares with n unit circles: . For n = 3, 8 , 9, 11, there are regions where three unit circles overlap but nowhere where more than 3 overlap]. Is this a provably strict bound?

Note 1: An example of the non-convex case mentioned above:



In above picture, the shaded non-convex region is the tile T and C is the circle. If the angle of the 'fan' portion of T divides 360, a suitable number n of unit Ts can cover the big circle. Then the 'core' of the big circle could have n T's overlapping. Note that the two circles are concentric and the inner one - core - is quite small (the radius of this core being much less than the length of the arc portion of the tile that is shown lying along the big circle periphery; iow, the core portion of each tile is a lot smaller than shown in the figure). And the same n units don't seem to be able to cover any bigger circle.

Note 2: One could also go to higher dimensions and ask if there is an upper bound on the number of tiles (which are 3d regions now) that can overlap in some part of space when n tiles cover a convex region C of maximum volume. And of course, other (non Euclidean - geometries.

Question 2:

'Erich's Packing Center' has lists of coverings such as 'equilateral triangles covering squares, squares covering circles and so on...'

Could we have any intuitive 'large scale' results such as (say):

a. "For any n, among all unit area triangular tiles of unit area, the equilateral triangle tile is the the one such that n units cover the largest square" . And if this claim is invalid, is it that for every n, that the triangular unit such that n units thereof covers the largest square has a different shape?

OR

b. "For any n, among all unit area rectangles, the square is the one such that n unit squares cover the largest circle"

.. indeed many such claims can be made but how many are valid?

Note (October 19th, 2018):
A further question could be posed:
Given a set of convex regions (call them covering tiles) with no constraint of equality among them and one tries to arrange them so that they together cover the largest (in terms of area or perimeter) convex region. Is there any upper bound on the number of covering tiles that can overlap somewhere?

The answer appears to be negative. Consider the following figure:

8 convex regions together cover a square. 4 of them are mutually identical isosceles triangles and at the center is a small region where these 4 covering tiles all overlap (the other 4 tiles are quadrilaterals as shown). Now, it appears that there is no convex region larger than the square that can be covered by this set of 8 covering tiles.
The construction appears generalizable to hexagons covered by 12 regions with 6 of these regions (all isosceles triangles) overlapping at the center, octagons covered by 16 tiles of which 8 overlap and so forth.

However, when the covering tiles have to be identical, one still has no example where more than 3 of the covering tiles overlap when together covering the largest possible convex region.

0 Comments:

Post a Comment

<< Home