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:
“Much more frequent in Hollywood than the emergence of Cinderella is her sudden vanishing. At our party, even in those glowing days, the clock was always striking twelve for someone at the height of greatness; and there was never a prince to fetch her back to the happy scene.”
—Ben Hecht (1893–1964)
“The power to guess the unseen from the seen, to trace the implications of things, to judge the whole piece by the pattern, the condition of feeling life in general so completely that you are well on your way to knowing any particular corner of it—this cluster of gifts may almost be said to constitute experience.”
—Henry James (1843–1916)