TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Thursday, November 23, 2017

Non-congruent Tilings of the Plane - Update



The good news: A paper by Andrey Kupavskii, Janos Pach and Gabor Tardos has answered the question (http://nandacumar.blogspot.in/2014/12/filling-plane-with-non-congruent-pieces.html) of tiling the plane with non congruent triangles of same area and perimeter - in the negative. Such a tiling cannot be done.

Here is their paper: https://arxiv.org/abs/1711.04504

These are early days but one wonders if their approach (with suitable modifications) can be generalized to tell us if the plane can be divided into pairwise non-congruent quadrilaterals (or even convex regions) all of equal area and perimeter.

Note: Dirk Frettloh has shown in his paper a year and some back how to cut a plane into quadrangles all of same area and *bounded* perimeter but not same perimeter.

One could add a further constraint to the fair tiling with non congruent quadrilaterals - that of the vertex to vertex (vtov) requirement. There seem to be 'more than' aleph_1 different quadrilaterals of same area and perimeter and 'only' aleph_0 are needed to cover the plane so (guess) if the vtov constraint is NOT enforced, one can probably pick and choose the tiles carefully and manage.

We could also ask: is it possible to tile the plane with non congruent convex tiles all of same area and perimeter but with no further constraints on say, the number of sides of each tile? Such a layout could be called a 'non-congruent fair tiling of the plane'.

Note (September 2018): The last question could perhaps be answered "yes" in the following way: Consider the convex fair partition problem for convex regions - now fully settled. One understands, the solution space is quite large at least when n is a prime power and so at least when n is a prime power, we have a good chance of achieving a fair partition of any convex region (at least a region lacking in symmetries) into mutually non-congruent tiles. Then, we could just keep scaling up the polygon being partitioned and increasing n correspondingly and this appears to guarantee a fair and non-congruent tiling of the plane. But this is only a crude existence argument and not a systematic algorithm to arrange some set of equal area and equal perimeter and mutually non-congruent tiles to tile the plane.

------------