Thurston's Height Condition
William Thurston (1990) describes a test for determining whether a simply-connected region, formed as the union of unit squares in the plane, has a domino tiling. He forms an undirected graph that has as its vertices the points (x,y,z) in the three-dimensional integer lattice, where each such point is connected to four neighbors: if x+y is even, then (x,y,z) is connected to (x+1,y,z+1), (x-1,y,z+1), (x,y+1,z-1), and (x,y-1,z-1), while if x+y is odd, then (x,y,z) is connected to (x+1,y,z-1), (x-1,y,z-1), (x,y+1,z+1), and (x,y-1,z+1). The boundary of the region, viewed as a sequence of integer points in the (x,y) plane, lifts uniquely (once a starting height is chosen) to a path in this three-dimensional graph. A necessary condition for this region to be tileable is that this path must close up to form a simple closed curve in three dimensions, however, this condition is not sufficient. Using more careful analysis of the boundary path, Thurston gave a criterion for tileability of a region that was sufficient as well as necessary.
Read more about this topic: Domino Tiling
Famous quotes containing the words height and/or condition:
“How frightening it is to have reached the height of human accomplishment in art that must forever borrow from life’s abundance.”
—Franz Grillparzer (1791–1872)
“If it is asserted that civilization is a real advance in the condition of man,—and I think that it is, though only the wise improve their advantages,—it must be shown that it has produced better dwellings without making them more costly; and the cost of a thing is the amount of what I will call life which is required to be exchanged for it, immediately or in the long run.”
—Henry David Thoreau (1817–1862)