Domino Tiling - Thurston's Height Condition

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.