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!

0 Comments:

Post a Comment

<< Home