Another new paper of mine, “Area-Universal Rectangular Layouts,” with Mumford, Speckmann, and Verbeek (my third recent coauthor named Kevin), just appeared on the arXiv. It's about designing cartograms (stylized maps) in such a way that they can be morphed so that their areas represent arbitrary quantitative data about the regions they depict. I'd like to discuss it in more detail soon, but first I wanted to talk about Birkhoff's representation theorem for finite distributive lattices, the subject of a Wikipedia article I worked on recently and a key tool in our rectangular layout paper.

A lattice is just a partially ordered family of elements in which for any two elements we can find a unique element that's greatest among elements smaller than or equal to both of them (their greatest lower bound, or “meet”) and a unique element that's least among elements greater than or equal to both of them (their least upper bound, or “join”). Two examples should be very familiar: the family of real numbers, with maximum as their join operation and minimum as their meet operation, forms a lattice, as does the family of all subsets of a given set S, with set union as the join operation and set intersection as the meet operation. In both of these examples the lattice is distributive: the join and meet operations satisfy the same distributive law satisfied by multiplication and addition.

Birkhoff's theorem, called by Stanley “the fundamental theorem of finite distributive lattices,” shows that finite distributive lattices and finite partial orders are really just the same thing in disguise. The elements of every finite distributive lattice can be represented as the lower sets of an underlying partial order that may be uniquely determined from the lattice (it's the lattice's ordering on the subset of elements that can't be formed as joins of smaller elements). The join operation on these lower sets is just set union, and the meet operation on these lower sets is just set intersection. Conversely the lower sets of any partial order, with these operations, form a distributive lattice. The significance of this equivalence for algorithms research is that the partial order is always at most as large as the lattice to which it corresponds and is often significantly smaller. So, if some object or collection of objects has the structure of a distributive lattice, it can be more efficient to perform computations on it by reducing it to its underlying partial order and working with that order instead of the lattice.

Although I had known of related infinite duality theorems for much longer (from Johnstone's Stone Spaces and Halmos' Lectures on Boolean Algebras), I first became of Birkhoff's theorem only a few years ago, when Jean-Claude Falmagne was first trying to persuade me to do the research that eventually became “Learning Sequences.” Falmagne's computerized education software models the possible states of a human learner as a knowledge space, a family of sets describing the test questions the learner is capable of answering. From psychological considerations Falmagne wanted to assume only that this set family was closed under unions. But, for computational efficiency, he added an assumption that it was also closed under intersections. As Jean-Claude told me then, Birkhoff's theorem implies that intersection-closed knowledge spaces correspond precisely to the quasiorders describing a strict prerequisite structure on the concepts being learned (one cannot learn multi-digit addition without first learning single-digit addition). For this application time is not the bottleneck: the assessment algorithms perform a Bayesian probability calculation that involves looking at all states of the knowledge space, and that would be true regardless of how the space is represented. However, memory usage and communication bandwidth are much bigger issues: the assessment software runs as a browser plugin that needs to be given a concise representation of the whole knowledge space, and the quasiorder provided by Birkhoff's theorem is exactly such a concise representation. Unfortunately the assumption of closure under intersections has no psychological basis, leads to a too-large family of sets, causes the system to ask too many questions to assess a student's knowledge, and leads to inaccurate predictions of what the student is ready to learn; the point of my learning sequences paper is to look for similarly space-efficient representations that can avoid making this bad assumption.

In the case of our new paper, Éric Fusy had shown that the rectangular layouts (partitions of a rectangle into rectangles) that share a common dual graph can be given a distributive lattice structure. The algorithmic part of our paper looks at this lattice more carefully and finds a description of the underlying partial order that is based directly on the geometry rather than (as one would get by blindly applying Birkhoff's theorem) based on internal structures within the lattice. The algorithms in the paper construct layouts that can be morphed to have arbitrary areas without changing the combinatorial structure of the layout; they do this by characterizing this morphability property in terms of the underlying partial order, using the characterization to search for an appropriate lower set in the partial order, and then using the Birkhoff correspondence to turn the lower set back into a rectangular layout. The resulting algorithms, based on Birkhoff's theorem, turn out to be much more efficient than a brute force approach of trying all possible layouts.