Abstract
dc:description.abstractA \emph{simple} $n$-\emph{Venn diagram} is a collection of $n$ simple intersecting closed curves in the plane where exactly two curves meet at any intersection point; the curves divide the plane into 2n distinct open regions, each defined by its intersection of the interior or exterior of each of the curves. A Venn diagram is \emph{reducible} if there is a curve that, when removed, leaves a Venn diagram with one less curve and \emph{irreducible} if no such curve exists. A Venn diagram is \emph{extendible} if another curve can be added, producing a Venn diagram with one more curve. Currently it is not known whether every simple Venn diagram is extendible by the addition of another curve. We show that all simple Venn diagrams with $5$ curves or less are extendible to another simple Venn diagram. We also show that for certain Venn diagrams, a new extending curve is relatively easy to produce. We define a new type of diagram of simple closed curves where each curve divides the plane into an equal number of regions; we call such a diagram a \emph{face-balanced} diagram. We generate and exhibit all face-balanced diagrams up to and including those with $32$ regions; these include all the Venn diagrams. Venn diagrams exist where the curves are the perimeters of polyominoes drawn on the integer lattice. When each of the 2n intersection regions is a single unit square, we call these \emph{minimum area polyomino Venn diagrams}, or \emph{polyVenns}. We show that polyVenns can be constructed and confined in bounding rectangles of size 2r \times 2c whenever $r, c \ge 2$ and $n=r+c$. We show this using two constructive proofs that extend existing diagrams. Finally, for even $n$, we construct polyVenns with $n$ polyominoes in (2n/2 - 1) \times (2n/2 + 1) bounding rectangles in which the empty set is not represented as a unit square.
Degree
thesis:*- Level thesis:degree_level
- Doctor of Philosophy Ph.D.
- Department thesis:degree_department
- Department of Computer Science
- Year dc:date.issued
- 2013
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Bultena, Bette
- Advisor dc:contributor.supervisor
-
- Ruskey, Frank
Subjects
dc:subject × 5Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
- Language dc:language.iso
- en, English
Identifiers
dc:identifier.*- Dc Identifier Citation
-
Bette Bultena, Branko Gr\"{u}nbaum, Frank Ruskey. ``Convex Drawings of Intersecting Families of Simple Closed Curves.'' 11th Canadian Conference of Computational Geometry, (1999): 33-54.
Bette Bultena, Frank Ruskey. ``Minimum Area Polyomino Venn Diagrams.'' Journal of Computation Geometry, 3(2012): 154-167.
Bette Bultena, Frank Ruskey. ``Venn Diagrams with Few Vertices.'' Electronic Journal of Combinatorics, 5(1998): R44.