Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is clear that any corner type of Wang Tile could be converted to edge type of Wang Tile by defining the edge color according to the corner color.

However, could we convert edge type of Wang Tile to corner tile so that each tiling of the corner tiles correspond to a (unique) tiling of the edge type of Wang tile?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

I assume that what you intend is that edge-type Wang tiles are squares with colored edges, and that adjacent squares in a tiling must have matching edge colors, and that corner-type Wang tiles have colored corners, so that in a tiling, all four squares around a vertex have the same color.

Now, it is clear, as you mention, that if we have a collection of corner-type Wang tiles, we can make a corresponding collection of edge-type Wang tiles, by coloring each edge with the ordered pair of colors on the corners. Matching these edges is equivalent to matching the corners in the original tiling and vice versa, so this reduces the corner-type tiling problem to the edge-type tiling problem.

Conversely, now, suppose that we have a collection $C$ of edge-type Wang tiles. Let us design a collection of corner-type tiles as follows. Consider the possible configurations of a valid $2\times 2$ array around a corner vertex. To each such configuration we may correspond the list of four edge colors $(a,b,c,d)$ corresponding to the (west,north, east, south) edges coming out of that vertex. Think of these $4$-tuples as the possible corner colors. Now, to form the corner-type tile set, for each edge-type tile

   --------------
   |     x      |
   |            |
   |w          y| 
   |            |
   |     z      |
   --------------

We add a tile of type

(w,x,.,.)   (.,x,y,.) 
   --------------
   |            |
   |            |
   |            | 
   |            |
   |            |
   --------------
(w,.,.,z)     (.,.,y,z)

where the colors are indicated at the corners, and the dots can be any color from the original edge-colors. Thus, each corner color here in effect gives information about the corresponding edge colors of the relevant edges, and no information about the other edges that will be at that corner.

If there is a tiling with the original edge-type Wang tile set $C$, then we can easily convert this to a tiling with the new corner-type tiles. And conversely, if we have a tiling with the new corner-type tiles, then because the corner colors match, each corner color in the tiling determines the edge colors, and these must arise as from tile types in $C$. Thus, we have reduced the edge-type tiling problem to the corner-type tiling problem.

Thus, the two kinds of tiling problems are reducible to one another.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.