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:
“I cannot help wondering sometimes what I might have become and might have done if I had lived in a country which had not circumscribed and handicapped me on account of my race, but had allowed me to reach any height I was able to attain.”
—Mary Church Terrell (1863–1954)
“Beautiful credit! The foundation of modern society. Who shall say that this is not the golden age of mutual trust, of unlimited reliance upon human promises? That is a peculiar condition of society which enables a whole nation to instantly recognize point and meaning in the familiar newspaper anecdote, which puts into the mouth of a distinguished speculator in lands and mines this remark:M”I wasn’t worth a cent two years ago, and now I owe two millions of dollars.””
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)