Random Dyadic Tilings of the Unit Square

Svante Janson, Dana Randall, Joel Spencer

Research output: Contribution to journalArticle

Abstract

A "dyadic rectangle" is a set of the form R = [a2-s, (a + 1)2-s] × [b2-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 2n 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.

Original languageEnglish (US)
Pages (from-to)225-251
Number of pages27
JournalRandom Structures and Algorithms
Volume21
Issue number3-4
DOIs
StatePublished - 2002

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Random Dyadic Tilings of the Unit Square'. Together they form a unique fingerprint.

  • Cite this