PDF《k -gons?》

Which n-Venn diagrams can be drawn with convex k-gons? Jeremy Carroll ? Frank Ruskey ? Mark Weston ? Abstract We establish a new lower bound for the number of sides required for the com- ponent curves of simple Venn diagrams made from polygons.

Speci?cally, for any n-Venn diagram of convex k-gons, we prove that k ≥ (2n ?

2 ? n)/(n(n ? 2)). In the process we prove that Venn diagrams of seven curves, simple or not, cannot be formed from triangles. We then give an example achieving the new lower bound of a (simple, symmetric) Venn diagram of seven convex quadrilaterals. Previously Gr¨ unbaum had constructed a symmetric 7-Venn diagram of non-convex 5-gons [ Venn Diagrams II , Geombinatorics 2:25-31, 1992].

1 Introduction and Background Venn diagrams and their close relatives, the Euler diagrams, form an important class of combinatorial objects which are used in set theory, logic, and many applied areas. Convex polygons are fundamental geometric objects that have been investigated since antiquity. This paper addresses the question of which convex polygons can be used to create Venn diagrams of certain numbers of curves. This question has been studied over several decades, for example [1, 2, 7, 8, 9]. See the on-line survey [12] for more information on geometric aspects of Venn diagrams. Let C = {C1, C2,Cn} be a family of n simple closed curves in the plane that are ?nitely intersecting. We say that C is a Venn diagram (or n-Venn diagram) if all of the 2n open regions X1 ∩X2 ∩・ ・ ・∩Xn are non-empty and connected, where each set Xi is either the bounded interior or the unbounded exterior of the curve Ci. If the connectedness condition is dropped the diagram is called an independent family. We can also think of the diagram as a plane edge-coloured graph whose vertices correspond to intersections of curves, and whose edges correspond to the segments of curves between intersections. Edges are coloured according to the curve to which they belong. A Venn diagram or ? HP Laboratories, Bristol, UK ? Department of Computer Science, PO BOX 3055, University of Victoria, Victoria, BC, Canada

1 independent family is simple if at most two curves intersect at a common point, i.e. every vertex has degree exactly four. Two diagrams are considered isomorphic if one can be transformed into the other, or its mirror image, by a continuous deformation of the plane. A polygon is a simple closed curve composed of ?nitely many line segments. We refer to those line segments as sides and the intersections of sides as corners. Let the term k-gon designate a convex polygon with exactly k sides. Observe that two k-gons can (?nitely) intersect with each other in at most 2k points. In this paper, we consider Venn diagrams and independent families composed of k- gons, for some k. Note that an edge of a k-gon, using the graph interpretation of a Venn diagram, may contain zero or more corners of the k-gon containing that edge. Note also that the corners of the component k-gons are not vertices in the graph interpretation of any diagram unless they intersect another curve at that corner. It will prove convenient, when considering simple diagrams, to assume that di?erent curves do not intersect at corners. Lemma 1.1. Every simple Venn diagram whose curves are polygons is isomorphic to one in which curves do not intersect at corners. Proof. Given a simple Venn diagram, the set of intersection points and corners is a ?nite set, call it I. Now suppose that curve C has a corner x that intersects one other curve and let s1 = (y, x) and s2 = (x, z) be two of the sides of C. De?ne a new point x that is close to x and on s1, x and is such that the triangle whose vertices are {x, x , z} does not contain any of the points of I other than x and z. The diagram obtained by replacing s1 and s2 by s1 = (y, x ) and s2 = (x , z) is still a Venn diagram since no regions are created or destroyed, and it is isomorphic to the original diagram. Furthermore, it has one fewer corner intersecting other curves so the result follows by induction. The proof of Lemma 1.1 does not apply in the non-simple case since extra regions could be created by replacing s2 by s2 if C intersected more than one other curve at some point on s2. By Lemma 1.1, it is clear that if a simple n-Venn diagram can be drawn with k-gons, it can also be drawn with j-gons for any j >