Random dyadic tilings of the unit square
Svante Janson, Dana Randall, Joel Spencer · Random Structures and Algorithms · 2002
Abstract A “dyadic rectangle” is a set of the form R = [ a 2 − s , ( a + 1)2 − s ] × [ b 2 − t , ( b + 1)2 − t ], where s and t are nonnegative integers. A dyadic tiling is a tiling of the unit square with dyadic rectangles. In this paper we study n ‐tilings, which consist of 2 n nonoverlapping dyadic rectangles, each of area 2 − n , whose union is the unit square. We discuss some of the underlying combinatorial structures, provide some efficient methods for uniformly sampling from the set of n ‐tilings, and study some limiting properties of random tilings. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 225–251, 2002