'Atomic' (?) Polygons
This is on a problem I worried quite a lot about a long time back:
Let us define 'tiling' of a polygonal region as cutting it up into *some finite number* of polygonal pieces (call these 'tiles') such that the tiles are identical ('congruent') to one another - the tiles *need not* be similar to the polygon being cut. I was trying to find polygons which do not admit *any* tiling.
I guessed at a quadrilateral (with all angles measuring irrational fractions of PI but summing to 2*PI) and tried to prove that it cannot be cut into any finite number of mutually identical tiles. The effort was but a partial success; however it resulted in this 'challenge'
at the 'Ponder This' column at IBM Research (where the problem has been presented a little differently; the solution given there is entirely theirs).
What has been worked out at 'Ponder' appears to be a stronger result than what I was trying to get. The quadrilateral described above not only is untile-able; it cannot be cut into a finite number of pieces which all have the same *set of angles*. ie, even if the tiles only need to have the same set of angles (ie. the *order* of the angles in each tile need not be the same), this quadrilateral cannot be tiled.
This implies perhaps that this example is an overkill - if one 'only' needed a polygon that resists breaking into identical tiles. For instance, one could perhaps easily find polygons which CAN be cut if only the sets of angles to be the same across all tiles but cannot be partitioned when the *sequence* of angles too needs to be same across the tiles (Just take a quadrilateral as above with irrational angles, take another with the same set of angles in a different order, scale one of these quadrilaterals a bit (scaling is probably not necessary) and weld them together at some edge. The new piece is very likely to resist any division that needs every tile to have the same sequence of angles. But if the sequence of angles in the tiles were not to matter, one simply needs to break along the weld).
Not sure if such an atomicity of polygons (as we saw above, one can think of different types of atomicities) with respect to tiling is of any further significance. But as far as I am aware, even very easy-to-state problems in this area are formidable; for instance, I guess it is open to decide if a polygon is a *'rep-tile'*, even for the case where the given polygon is a *'polyomino'* - a very strong restriction.
Note: 'Dissection' is a more precise word for cutting polygons but I don't know what to call the pieces resulting from a dissection!
Let us define 'tiling' of a polygonal region as cutting it up into *some finite number* of polygonal pieces (call these 'tiles') such that the tiles are identical ('congruent') to one another - the tiles *need not* be similar to the polygon being cut. I was trying to find polygons which do not admit *any* tiling.
I guessed at a quadrilateral (with all angles measuring irrational fractions of PI but summing to 2*PI) and tried to prove that it cannot be cut into any finite number of mutually identical tiles. The effort was but a partial success; however it resulted in this 'challenge'
at the 'Ponder This' column at IBM Research (where the problem has been presented a little differently; the solution given there is entirely theirs).
What has been worked out at 'Ponder' appears to be a stronger result than what I was trying to get. The quadrilateral described above not only is untile-able; it cannot be cut into a finite number of pieces which all have the same *set of angles*. ie, even if the tiles only need to have the same set of angles (ie. the *order* of the angles in each tile need not be the same), this quadrilateral cannot be tiled.
This implies perhaps that this example is an overkill - if one 'only' needed a polygon that resists breaking into identical tiles. For instance, one could perhaps easily find polygons which CAN be cut if only the sets of angles to be the same across all tiles but cannot be partitioned when the *sequence* of angles too needs to be same across the tiles (Just take a quadrilateral as above with irrational angles, take another with the same set of angles in a different order, scale one of these quadrilaterals a bit (scaling is probably not necessary) and weld them together at some edge. The new piece is very likely to resist any division that needs every tile to have the same sequence of angles. But if the sequence of angles in the tiles were not to matter, one simply needs to break along the weld).
Not sure if such an atomicity of polygons (as we saw above, one can think of different types of atomicities) with respect to tiling is of any further significance. But as far as I am aware, even very easy-to-state problems in this area are formidable; for instance, I guess it is open to decide if a polygon is a *'rep-tile'*, even for the case where the given polygon is a *'polyomino'* - a very strong restriction.
Note: 'Dissection' is a more precise word for cutting polygons but I don't know what to call the pieces resulting from a dissection!
posted by R.Nandakumar @ 7:11 AM
2 Comments:
At 11:29 AM,
Anonymous said…
Could you point to some references/books on polygons and dissections/triangulations/tilings? Thanks.
And, thanks for the link!
At 8:31 PM,
R.Nandakumar said…
vishnu,
as far as i know, the best starting point for any online search in these domains is david eppstein's 'geometry junkyard'. eppstein has done a lot of work on dissections, mesh generation etc.. and many of his papers are available there plus many other facts. web pages of erik demaine, jeff erikson etc.. could be very useful as well.
as for books, the best book to hook up (and get hooked to!) computational geometry is o'rourke's 'computational geometry in c'. there is a more modern and somewhat more detailed book by de berg et al. which also i find very interesting.
for more of an insider's perspective than above, you should watch 'geomblog' or 'mp's page.
Post a Comment
<< Home