TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Friday, September 28, 2018

'Almost Right' - Fair Partitions and Non-Congruent Tiling

An interesting discussion took place around the 23rd minute of this lecture by Gabor Tardos:

https://www.birs.ca/events/2018/5-day-workshops/18w5058/videos/watch/201802080934-Tardos.html

The topic of the lecture: The impossibility of tiling the plane with pairwise non-congruent triangles all of the same area and perimeter.

A question came up from the audience: What if we retain the mutual non-congruence but instead of equality, allow both area and perimeter to be all within a few percent of one another?

A nice and simple answer too came up instantly: Take any tiling of the plane into identical triangles and simply perturb each vertex in the layout slightly - each in a different way. Intuitively, this achieves a non-congruent partition into triangles with areas and perimeters close to one another within any arbitrarily chosen bound. So, the impossibility happens only when one asks for areas and perimeters of the mutually non-congruent triangles to be precisely equal; allow both quantities even a slight but finite epsilon margin and there seem to be infinitely many ways to get the job done.

Concluding that discussion, Prof. Tardos remarked: "if you think two minutes, you can come up with a similar nice question which won't be easy at all to solve!"

Remark: There seems to be a fundamental difference between tiling with non-congruent rectangles and the fair partition / spicy chicken problem - cutting a convex region into n convex pieces of same area and same perimeter (proved possible for any n only very recently, after over a decade of efforts). For fair partition, it does not look anywhere near obvious that if we allow the pieces to have areas and perimeters to differ by some epsilon fraction, such an 'approximately fair partition' can be done easily.

Of course, I don't really know if the difference between these problems is a fundamentally interesting one!

Wednesday, September 26, 2018

Beyond Rep-tiles

A rep-tile is a shape that can be cut into smaller copies of the same shape - https://en.wikipedia.org/wiki/Rep-tile

Doubt: Is there a triangle T such that a certain number of T's can tile a triangle dissimilar to T?

Trivial example: 2 copies of right triangles tile an isosceles triangle dissimilar to the right triangle. An equilateral triangle is tiled by 3 mutually identical triangles which are not equilateral.

So the question is whether there are more non-trivial such examples, say, a triangle that can be tiled by 5 or 6 or n (but not less) mutually identical triangles that are dissimilar to itself.

Is there any quadrilateral that can tile a quad that is dissimilar to itself?

Again there is the trivial example of two copies of a trapezium with two angles = 90 degrees together forming a rectangle. Again, are there more non-trivial examples?

An equilateral triangle can be cut into 3 identical quadrilaterals that meet at its centroid. So one can ask, is there any triangle that allows partition into some other finite number of identical quadrilaterals.

And these questions have obvious 3d generalizations. Trivial examples can again be made by lofting the 2d trivial examples into prisms. And a regular tetrahedron can be cut into 4 identical tets that are dissimilar to the regular one.

-----------

A doubt about a theorem by Kantarovich:

Theorem (as I understand it): Given any planar convex region P and a set of n points, we can shoose weights for each point such that a weighted Voronoi partition of P with these points as nuclei is an equipartition. And if these points are moved continuously, the weights for which they yield an equipartition also change continuously.

Doubt: Is it guaranteed that if one insists all weights to be 1, there is a set of nuclei that gives an equipartition? Do Voronoi partitions with such special sets of points have any further properties?

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.