Minimum Area Venn Diagrams Whose Curves are Polyominoes

Stirling Chow and Frank Ruskey Department of Computer Science

University of Victoria

Victoria, B.C., Canada V8W 3P6

                                              schow@cs.uvic.ca

While working at the Berlin Academy, the renowned Swiss mathematician Leonard Euler was asked to tutor Frederick the Great’s niece, the Princess of Anhalt-Dessau, in all matters of natural science and philosophy [15]. Euler’s tutelage of the princess continued from 1760 to 1762 and culminated in the publishing of the popular and widely-translated “Letters to a German Princess” [8]. In the letters, Euler eloquently wrote about diverse topics ranging from why the sky was blue to free will and determinism.

In his lesson on categorical propositions and syllogisms, Euler used diagrams comprised of overlapping circles; these diagrams became known as Eulerian circles, or simply Euler diagrams. In an Euler diagram, a proposition’s classes are represented as circles whose overlap depends on the relationship established by the proposition. For example, the propositions

All arachnids are bugs Some bugs are cannibals

can be represented by Fig. 1.

In 1880, a Cambridge priest and mathematician named John Venn published a paper studying special instances of Euler diagrams in which the classes overlap in all possible ways [25]; although originally applied to logic reasoning, these Venn diagrams are now commonly used to teach students about set theory. For example, the Venn diagram in Fig. 2 shows all the ways in which three sets can intersect. The primary difference between Venn

Figure 1: An example of an Euler diagram.

and Euler diagrams is how they represent empty sets (e.g., the set of arachnids which are not bugs in the example of Fig. 1). In an Euler diagram, regions representing empty sets are omitted, while in Venn diagrams they are included but denoted by shading.

Informally, an n-Venn diagram is a set of n simple, closed curves that subdivide the plane into 2^{n} connected regions with each region uniquely mapping to a subset of the n curves depending on which curves enclose it. The regions are usually referred to by their enclosing curves. For example, the 3-Venn diagram in Fig. 2 with curves {A, B, C} has regions {∅, A, B, C, AB, AC, BC, ABC}. If an n-Venn diagram’s curves are equivalent to each other modulo translations, rotations, and reflections, then the diagram is referred to as a congruent n-Venn diagram.

In recent years, there has been renewed interest in studying the combinatorial and geometric properties of Venn diagrams [6, 22]. Of paramount importance is how to draw a Venn diagram for a given number of sets. John Venn proposed an iterative algorithm in his original Venn paper [25]; unfortunately, the resulting drawings lacked an aesthetic appeal. In 1989, Anthony Edwards developed an elegant method for drawing n-Venn diagrams that produced highly symmetric drawings [5]. Figure 3 shows a comparison of 5-Venn diagrams drawn using Venn’s and Edwards’ algorithms.

A  B C A ∩ C  B ∩ C A ∩ B A ∩ B ∩ C ∅

Figure 2: A Venn diagram that represents the Euler diagram in Fig. 1 by shading the missing regions.

Figure 3: A 5-Venn diagram drawn iteratively using Venn’s and Edwards’ algorithms; the last curve drawn is highlighted.

Figure 4: (a) A symmetric 5-Venn diagram using ellipses and (b) a 6-Venn diagram using triangles.

An interesting problem popularized by Grünbaum [11, 12, 13, 14] is to consider which Venn diagrams can be drawn using specific shapes. Figure 2 shows a 3-Venn diagram comprised of circles; a natural question to ask is if such a diagram exists for four sets. It turns out the answer is no, and this can be proved easily using Euler’s formula (V = E − F + 2) and noting that such a diagram must have 2^{4} = 16 faces and that two circles can intersect at at most two points [22]. Figure 4 shows examples of Venn diagrams drawn using ellipses [11] and triangles [3]. The diagram in Fig. 4(a) is special because it is an example of a symmetric Venn diagram; that is, a diagram with n-fold rotational symmetry and (necessarily) congruent curves. Symmetric Venn diagrams exist if and only if n is prime [10].

On his “Math Recreations” web site [24], Mark Thompson proposed the novel problem of finding Venn polyominoes (from now on referred to as npolyVenns); these are Venn diagrams whose curves are the outlines of polyominoes. Polyominoes, or n-ominoes, are a generalization of dominoes (2ominoes) whereby shapes are formed by gluing together n unit squares. One can also think of a polyomino as being the result of cutting a shape from a piece of graph paper where the cuts are made along the lines. Thompson found examples of congruent n-polyVenns for n = 2, 3, 4, and using a computer search, we found a congruent 5-polyVenn; these are shown in Fig. 5.

In the remainder of this paper, our focus is on minimizing the total area of the drawing (relative to a scaling factor). We present some examples that minimize area according to various additional constraints. At present, these examples do not generalize and so we develop an algorithm that comes close to minimizing the area. The algorithm is simple and utilizes symmetric chain decompositions of the Boolean lattice. We also provide asymptotic results that relate the area required by the algorithm’s diagrams to the theoretical minimum area. We conclude by presenting some open problems related to Venn polyominoes and other shape-constrained Venn diagrams.

Polyominoes

A polyomino is an edge-connected set of unit squares, called cells, embedded in the plane. Polyominoes are often classified by area and referred to as nominoes when they contain n cells. For example, the games of dominoes and Tetris are played with 2-ominoes and 4-ominoes (tetrominoes), respectively (see Fig. 6).

Polyominoes have been extensively studied and have a wide-range of applications in mathematics and the physical sciences [9, 17]. The problem of counting n-ominoes has garnered considerable interest [16, 19, 21], and although counts up to 47-ominoes are known (see sequence A001168 [23]), the problem of finding a formula for the number remains open.

Several other subclasses of polyominoes have been defined. Free polyominoes treat polyominoes that are translations, rotations, or reflections of each other to be equivalent whereas fixed polyominoes only consider translations as being equivalent. For example, Fig. 6 shows the 19 equivalence classes of fixed tetrominoes and 5 equivalence classes (a,b,c,d, and e), of free Figure 5: (a)–(c) Mark Thompson’s congruent n-polyVenns for n = 2, 3, 4 and (d) the authors’ congruent 5-polyVenn; in each case, curve A is highlighted.

Figure 6: All possible 4-ominoes (tetrominoes) 7

Figure 7: 10-ominoes that exhibit different convexivity properties.

tetrominoes.

If every column (row) of a polyomino is a contiguous strip of cells then the polyomino is called column-convex (row-convex). A convex polyomino is one that is both column and row convex (see Fig. 7). No closed-form formula is known for the number, a(n), of fixed column-convex n-ominoes; however, Pólya [20] derived the recurrence relation a(n) = 5a(n − 1) − 7a(n − 2) + 4a(n − 3) with a(1) = 1, a(2) = 2, a(3) = 6, and a(4) = 19.

Minimum Area n-polyVenns

An n-polyVenn is a Venn diagram comprised of n curves, each of which is the perimeter of some polyomino. In particular, each polyomino must be free of holes in order for the perimeter to be a simple, closed curve, and when placed on top of another polyomino, may not partially cover any of the bottom polyomino’s cells (i.e., the corners of the curves must have unit coordinates).

Referring to the examples in Fig. 5, we see that an n-polyVenn can be drawn by tracing the curves on the lines of a piece of graph paper; in the (combinatorial) graph drawing community, this is referred to as an orthogonal grid drawing [2]. In fact, any orthogonal grid drawing of a Venn diagram will produce curves that are the perimeters of polyominoes. A bit of thought should convince you that each of an n-polyVenn’s 2^{n} regions must contain at least one cell; therefore, the minimum area for such a diagram is 2^{n} − 1 cells (−1 since the empty set region is the exterior). In addition, since each curve encloses 2^{n−1} regions, it must be the perimeter of at least a 2^{n−1}-omino. This leads us to the following definition of a minimum area n-polyVenn:

Definition

A minimum area n-polyVenn is an orthogonal unit-grid drawing of a Venn diagram with area 2^{n} − 1 and whose curves have area 2^{n−1}.

All the Venn diagrams in Fig. 5 are minimum area congruent n-polyVenns. By trial-and-error, we have also found minimum area non-congruent n-polyVenns for n = 6, 7 (see Figs. 8,9). It is unknown if minimum area n-polyVenns exist for n ≥ 8, although we suspect there is an upper limit due to the rigid constraints of orthogonal grid drawings.

Orthogonal grid drawings of Venn diagrams were first studied by Eloff and van Zijl [7]; they developed a heuristic algorithm based on a greedy incremental approach. An optimization step in the algorithm attempted to reduce the overall area of the diagram, but there was no upper bound. In addition, their algorithm produced polyominoes with holes, so the resulting diagrams would not be considered Venn diagrams in the formal sense (because the sets were not represented by simple, closed curves).

In the following sections, we present algorithms for approximating minimum area n-polyVenns. The first algorithm is trivial and produces npolyVenns with less than 3/2 times the minimum area. The second algorithm improves upon the first by using symmetric chain decompositions of the Boolean lattice and produces n-polyVenns whose areas are asymptotically minimum.

There is another definition of area based on the w × h bounding box that contains an n-polyVenn; such a box must also have at least one cell to represent the empty set. For example, the n-polyVenns in Fig. 5 are contained by 4 × 1, 2 × 5, 5 × 5, and 7 × 7 bounding boxes, respectively. Since an n-polyVenn must be comprised of at least 2^{n} − 1 cells, a bounding box must have area at least 2^{n}. This leads us to the following definition of a Figure 8: A minimum area 6-polyVenn.

10 Figure 9: A minimum area 7-polyVenn.

11 minimum bounding box n-polyVenn:

Definition

A minimum bounding box n-polyVenn is an orthogonal unit-grid drawing of a Venn diagram that is enclosed by a 2^{s} × 2^{t} rectangle where s + t = n.

Of the congruent n-polyVenns in Fig. 5, only (a) is a minimum bounding box n-polyVenn. Figure 10 shows some examples of minimum bounding box non-congruent n-polyVenns.

At present, we leave minimum bounding box n-polyVenns and focus the rest of this paper on minimum area n-polyVenns.

A 3/2-APPROX Algorithm

This algorithm is best explained by way of an example. Suppose we wish to draw a 5-polyVenn with the curves {A, B, C, D, E}. We begin by drawing a 1 × 14 rectangle and labelling it as region ABCDE; in other words, the curves are 1 × 14 rectangles stacked on top of each other. We now place 30 cells around the perimeter of ABCDE and uniquely label them with the 30 remaining non-empty regions; the result is shown in Fig. 11. After adding the perimeter cells, each curve becomes a polyomino formed by the original 1 × 14 rectangle with “bumps” wherever the curve encloses a perimeter cell.

In the general case, this algorithm will produce an n-Venn polyomino beginning with a 1 × (2^{n−1} − 2) rectangle that has a perimeter of 2^{n} − 2 (for the 2^{n} regions less the empty and full sets). The resulting diagrams have an area of 2^{n} +2^{n−1} −4 which is less than 3/2 times the minimum area of 2^{n} −1.

An Asymptotically Optimal Algorithm

The previous algorithm can be significantly improved by noting that not all regions need to be placed adjacent to the initial rectangle; instead, if region X is a subset of region Y then X can be placed directly above or below Y Figure 10: Minimum bounding box n-polyVenns for 2 ≤ n ≤ 5.

13 Figure 11: A naïve approximation for a minimum area 5-polyVenn; curve A is highlighted

(depending on if Y is above or below the initial rectangle), and the curves will remain as polyomino perimeters. This chaining of regions can continue as long as the subset property is maintained. Figure 12 shows an example of 5-polyVenn that chains regions as much as possible. Note also that the resulting polyominoes are column-convex.

When regions are chained, a smaller perimeter is needed for the initial rectangle and so the total area of the diagram is reduced. A smaller area diagram is created by minimizing the number of chains, so the question arises as to the best way to decompose the regions into chains; for this question, we need to use a result from the theory of partially ordered sets.

Given a set S with powerset P(S), we define the partially ordered set (poset) B(S) with elements P(S) ordered by inclusion. Since B(S) is closed under union, intersection, and complement, it is a Boolean lattice. Figure 13(a) shows an example of B({A, B, C, D}).

Let |S| = n. A symmetric chain decomposition (SCD) of B(S) is a partition of S into \binom{n}{⌊n/2⌋)} symmetric chains. Each symmetric chain is a sequence of subsets x_{1}, x_{2}, …, x_{t} with the following properties:

x_{i} ⊂ x_{i+1} for all 1 ≤ i < t,  (1)
|x_{i}| = n − |x_{t−i+1}| for all 1 ≤ i ≤ ⌈t/2⌉.  (2)

Symmetric chain decompositions form an essential ingredient of the recent proof of Griggs, Killian and Savage [10] that symmetric Venn diagrams exist if and only if the number of curves is prime.

Figure 12: An approximation for a minimum area 5-polyVenn using columnconvex polyominoes and symmetric chains; curve A is highlighted.

\begin{aligned}& ∅ \\ ∅ \end{aligned}

Figure 13: (a) The poset B({A, B, C, D}), (b) one of its symmetric chain decompositions, and (c) the resulting 4-polyVenn.

Several algorithms exist for decomposing B(S) into symmetric chains; we describe two of these algorithms below. The first, due to de Bruijn, van Ebbenhorst Tengbergen, and Kruyswijk [4] is called the Christmas tree pattern by Knuth [18]. It is an inductive construction that creates a set T_{n} of \binom{n}{⌊n/2⌋} chains. Initially T_{1} = \{∅ ⊂ \{1\}\}. To obtain T_{n} from T_{n−1}, take each chain x_{1} ⊂ x_{2} ⊂ ⋯ ⊂ x_{t} in T_{n} and replace it with the two chains x_{2} ⊂ ⋯ ⊂ x_{t} and x_{1} ⊂ x_{1} ∪ {n} ⊂ x_{2} ∪ {n} ⊂ ⋯ ⊂ x_{t} ∪ {n} in T_{n+1} if t > 1. If t = 1 the first chain is empty and is ignored.

A second method, due to Aigner [1], can be described as a greedy lexicographic algorithm. It is efficient and easy-to-implement, and is the method that we used in creating the example diagrams. Let m(x, y) be the smallest element in a set x that is not in the set y, where m(x, y) = −∞ if x ⊂ y. We say that x is lexicographically smaller than y if m(x, y) < m(y, x). In Aigner’s algorithm, the following process is repeated until every element of B({1, 2, …, n}) is contained in some chain. For k = 0, 1, 2, …, n, denote by R(k) the set of subsets of {1, 2, …, n} size k that are not yet in any chain. Let j be the smallest value for which R(j) is non-empty and let x be the lexicographically smallest set in R(j). The set x becomes the smallest set in a new chain x = x_{1} ⊂ x_{2} ⊂ ⋯ ⊂ x_{t}. The successive elements of this chain are obtained by taking x_{i+1} ∈ R(i + 1) to be the lexicographically smallest set that contains x_{i}. It is by no means obvious that this algorithm is correct, but indeed it is!

Because of their subset property (1), the symmetric chains can be directly used to layout the regions of an n-polyVenn. Figure 13(b) shows the SCD of B({A, B, C, D}) that is produced by Aigner’s algorithm, and Fig. 13(c) shows the resulting 4-polyVenn. The 5-polyVenn in Fig. 12 was also produced from Aigner’s SCD of B({A, B, C, D, E}).

In the general case, this algorithm will produce an n-polyVenn beginning with a 1 × (\binom{n}{⌊n/2⌋} − 2)/2 rectangle that has a perimeter of \binom{n}{⌊n/2⌋}. The resulting diagrams have an area of (\binom{n}{⌊n/2⌋)−2}/2 + 2^{n} − 2. By using Stirling’s approximation of \binom{n}{n/2} ∼ 2^{n}/\sqrt{πn/2}, one can show that the algorithm produces diagrams whose area is 1 + O(1/\sqrt{n}) times the minimum area of 2^{n} − 1; therefore, as n increases, the approximation gets asymptotically close to optimal.

Open Problems and Final Remarks

To close the paper, we list some open problems that are inspired by the examples in this paper. With the exception of the congruent n-polyVenns, the examples in this paper were constructed by hand, and it is very likely that relatively naïve programs will be able to extend them. Such extension would be interesting, but even more interesting would be general results that apply for arbitrary numbers of curves.

1. Are there congruent n-polyVenns for n ≥ 6? Figure 5 shows that they exist for n = 2, 3, 4, 5.

2. Is there a 5-polyVenn whose curves are convex polyominoes? (The curves in Figure 5(d) are not both row-convex and column-convex polyominoes.)

3. Are there minimum bounding box n-polyVenns for n ≥ 6? Figure 10 shows that they exist for n = 2, 3, 4, 5.

4. Are there minimum area n-polyVenns for n ≥ 8? Figure 9 shows one for n = 7.

5. One problem for which we have not attempted solutions is the construction of n-polyVenns that fill an w × h box, where wh = 2^{n} − 1. Of course, a necessary condition is that 2^{n} − 1 not be a Mersenne prime. For example, is there are 4-polyVenn that fits in a 3 × 5 rectangle or a 6-polyVenn that fits in a 7 × 9 or 3 × 27 rectangle?

References

[1] Martin Aigner, Lexicographic math in Boolean algebras, Journal of Combinatorial Theory, Series B 14 (1973), pp. 187–194.

[2] Guisseppi Battista, Peter Eades, Roberto Tomassia, and Ionnis Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice-Hall, 1999.

[3] Jeremy Carroll, 6-Venn Triangle Problem, Personal Homepage,

http://www.hpl.hp.com/personal/jjc/index.html.

[4] N.G. de Bruijn, C. van Ebbenhorst Tengbergen, and D. Kruyswijk, On the set of divisors of a number, Nieuw Archief voor Wiskunde 2 (1951), pp. 191–193.

[5] Anthony W. F. Edwards, Venn diagrams for many sets, New Scientist 7 (1989), pp. 51–56.

[6] Anthony W. F. Edwards, Cogwheels of the Mind: The Story of Venn Diagrams, The Johns Hopkins University Press, 2004.

[7] Jacques Eloff and Lynette van Zijl, An incremental construction algorithm for Venn diagrams, SAICSIT 2000, Cape Town, South Africa, November 2000.

[8] Leonard Euler, Lettres a une Princesse d’Allemagne sur Divers Sujets de Physique et de Philosophie, Imperial Academy of Sciences, Petersburg, 1768–1772.

[9] Solomon Golomb, Polyominoes: puzzles, patterns, problems, and packings, Princeton University Press, 1994.

[10] Jerrold Griggs, Charles E. Killian, and Carla D. Savage, Venn diagrams and symmetric chain decompositions in the Boolean lattice, Electronic Journal of Combinatorics, 11 (2004).

[11] Branko Grünbaum, Venn diagrams and Independent Families of Sets, Mathematics Magazine 48 (Jan-Feb 1975), pp. 12–23.

[12] Branko Grünbaum, Venn diagrams I, Geombinatorics (Vol. I) 4 (1992), pp. 5–12.

[13] Branko Grünbaum, Venn diagrams II, Geombinatorics (Vol. II) 2 (1992), pp. 25–32.

[14] Branko Grünbaum and Peter Winkler, A Venn diagram of 5 triangles, Mathematics Magazine 55 (1982), pg. 311.

[15] Ioan James, Remarkable Mathematicians: From Euler to von Neumann, Cambridge University Press, 2002.

[16] Iwan Jensen and Anthony J. Guttmann, Statistics of lattice animals (polyominoes) and polygons, Journal of Physics, Series A 33 (2000), pp. L257–L263.

[17] David A. Klarner, Some results concerning polyominoes, Fibonacci Quarterly 3 (1965), pp. 9–20.

[18] Donald E. Knuth, The Art of Computer Programming, pre-fascicle 4A (a draft of Section 7.2.1.6: generating all trees), Addison-Wesley, 2004.

[19] Stephan Mertens, Counting lattice animals: a parallel attack, Journal of Statistical Physics 66 (1992), pp. 669–678.

[20] George Pólya, On the number of certain lattice polygons, Journal of Combinatorial Theory 6 (1969), pp. 102–105.

[21] D.H. Redelmeier, Counting polyominoes: yet another attack, Discrete Mathematics 36 (1981), pp. 191–203.

[22] Frank Ruskey, A survey of Venn diagrams, Electronic Journal of Combinatorics 4 (1997), DS #5 (updated 2001).

[23] Neil J.A. Sloane, The On-Line Encyclopedia of Integer Sequences,

http://www.research.att.com/~njas/sequences/.

[24] Mark Thompson, Venn polyominoes, Math Recreations,

http://www.flash.net/~markthom/html/venn_polyominos.html.

[25] John Venn, On the diagrammatic and mechanical representation of propositions and reasonsings, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 9 (1880), pp. 1–18.