Minimum Area Venn Diagrams whose Curves are Polyominoes

Stirling Chow, Department of Computer Science, University of Victoria, Canada.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.

Abstract:

Venn diagrams are collections of simple closed curves in the plane with the property that intersection of the interiors of any subcollection of the curves must be a non-empty connected region. Here we consider the curves to be the boundaries of polyominoes. If there are n polyominoes, then in a minimum area Venn diagram the area of each polyomino is 2n-1. We give examples of minimum area Venn diagrams for n = 2,3,4,5,6,7 and an approximation algorithm that gives Venn diagrams of asymptotically minimum area.

Example:

The example below consists of 6 polyominoes and how they should be placed relative to each other to form a minimum area Venn diagram.

For the example above, we show below a coloring of each region of the Venn diagram according to how many polyominoes cover that square: red = 1, yellow = 2, green = 3, cyan = 4, blue = 5, and black = 6.



Selected papers that refer to this one:
Several of the open problems posed in this paper have been solved. Except where noted all of the diagrams linked below are due to Bette Bultena.

News Flash!

Several of the open problems in the paper have been solved by a nice construction of Matthew Klimesh, and by some constructions of Bette Bultena inspired by those of Klimesh. In particular, minimum area Venn diagrams exist for all n, and they can be put in boxes of various aspect ratios. These constructions will be written up in a paper in due course, but for now, here are some teasers!


Back to list of publications.