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 nonempty
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 2^{n1}.
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.

The pdf file.
The postscript file.
Please send me a note if
you download one of these files.
It's always nice to know who's reading your papers.

Appears in Mathematics Magazine, Volume 80, No. 2, April 2007, pp. 91103.

Submitted March 2, 2005.

Mark Thompson's page on
Venn
Polyominos is what got us started on this research.

For more on Venn diagrams check out the Survey
of Venn Diagrams, Dynamic Survey #5 at the
Electronic Journal of Combinatorics.

A relevant reference that we should have included is
David W. Henderson, Venn diagrams for more than four classes,
American Mathematical Monthly, American Mathematical Monthly, 70 (1963)
424–426. That paper contains the necessary condition that
n is prime in any symmetric nVenn diagram.
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.

A 3x5 diagram (no empty set): link.
Note that all the polyominoes are convex.

A 7x9 diagram (no empty set): link.

An 8x8 diagram: link.
Another 8x8 diagram (by Abdolkhalegh Ahmadi):
link.
Note that the rightmost 4 columns form the 4x8 diagram
from the paper.

An 8x16 diagram: link.
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.