Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Tile invariants: new horizons
Pak I. Theoretical Computer Science303 (2-3):303-331,2003.Type:Article
Date Reviewed: Feb 24 2004

The tiling problem can best be described by thinking of the problem of covering a checkerboard with dominoes. One can generalize the problem by allowing other shapes of the board, changing it to have infinite dimensions, allowing for holes in the board, building it out of triangles rather than squares, or going to higher dimensions. The dominoes may similarly be generalized to have various shapes, made of the same building blocks as the board. In many cases, the covering may become impossible, or very difficult to find. Various techniques, like coloring and height functions, have been developed to analyze the problem for various kinds of boards and tiles. The author of this paper is the originator of a new technique in this genre, called tile invariants. Given a covering, we can visualize various linear relationships that we need to apply between the number of tiles of different kinds used in the covering.

Given this rather new technique, and because the abstract promised a survey, I expected that the paper would be a good introduction to this entire field. However, it appears that the best way to learn about this field is to read Pak’s three previous papers in this area [1,2,3], starting with the earliest. If the style of presentation in those is similar to that in the present paper, then one would also have to first develop the ability to visualize the concrete underpinnings of the problems, even when they are stated in the most general terms possible. One would also need to appreciate the group theoretic discussions, and the results of an examination of the computational feasibility of constructing the groups without needing to see their relationship with the tiling problem.

A short monograph on the groups of tile invariants, written for the general reader, would be a welcome addition to the literature. I think that even some seasoned mathematicians would benefit from such a monograph.

Reviewer:  Ranan Banerji Review #: CR129135 (0408-0963)
1) Pak, I. Ribbon tile invariants. Transactions of the American Mathematical Society 352, 12 (2000), 5525–5561.
2) Moore, C.; Pak, I. Ribbon tile invariants from signed area. Journal of Combinatorial Theory - Series A 98, 1 (2002), 1–16.
3) Muchnik, R.; Pak, I. Tilings by ribbon tetrominoes. Journal of Combinatorial Theory - Series A 88, 1 (1999), 188–193.
Bookmark and Share
 
Permutations And Combinations (G.2.1 ... )
 
 
Combinatorial Algorithms (G.2.1 ... )
 
 
Computations On Polynomials (F.2.1 ... )
 
 
Markov Processes (G.3 ... )
 
 
Combinatorics (G.2.1 )
 
 
Numerical Algorithms And Problems (F.2.1 )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "Permutations And Combinations": Date
Computing short generator sequences
Driscoll J., Furst M. Information and Computation 72(2): 117-132, 1987. Type: Article
Jan 1 1988
Permutations of bounded degree generate groups of polynomial diameter
McKenzie P. (ed) Information Processing Letters 19(5): 253-254, 1984. Type: Article
Aug 1 1985
How to construct pseudorandom permutations from pseudorandom functions
Luby M. (ed), Rackoff C. SIAM Journal on Computing 17(2): 373-386, 1988. Type: Article
Jul 1 1989
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy