Minimum Area Venn Diagrams Whose Curves are Polyominoes

Details Minimum Area Venn Diagrams Whose Curves are Polyominoes Minimum Area Venn Diagrams Whose Curves are Polyominoes

2006-03-03

arxiv.org/abs/math/0603068v1

Mathematics

Combinatorics

20 pages, 13 figures

Scientific paper

Venn diagrams are a graphical way to represent a set system. Each of the n sets is represented by a simple closed curve. The n curves subdivide the plane into 2^n open connected regions, each of which represents the intersection of its containing curves' sets. For example, two overlapping circles can divide the plane into 4 regions representing {}, A, B, and A intersect B. Three overlapping circles can also be used to represent the 2^3 ways in which 3 sets can intersect. One of the primary questions related to Venn diagrams concerns which shapes can be used for the curves. The previous examples used 2 and 3 circles, but a 4-set Venn diagram cannot be represented by 4 circles; instead, ellipses must be used. In this paper, we consider Venn diagrams whose curves are the outlines of polyominoes. In particular, we give examples of Venn diagrams where the curves are rotations and translations of a single polyomino, so-called congruent polyVenn diagrams. We also consider the problem of area-minimization (relative to a scaling factor) and present examples of Venn polyominoes which minimize area according to various 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.

Affiliated with

Also associated with

No associations

Rating

Minimum Area Venn Diagrams Whose Curves are Polyominoes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum Area Venn Diagrams Whose Curves are Polyominoes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Area Venn Diagrams Whose Curves are Polyominoes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-118500