From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: Asking for help in finding points of intersection between more ellipses Date: 12 Mar 1999 17:58:20 GMT Newsgroups: sci.math Keywords: Unbounded number of regions as intersection of convex polygons Some neophyte named Dave Rusin wrote: > It certainly seems to be true that it is impossible to represent all the > Boolean combinations of _five_ sets by using five _convex_ subsets of R^2. Robin Chapman responded: > Don't bother. One *can* represent all Boolean combinations of any finite > number of sets by using convex subsets of the plane. This is an exercise > (with solution) in Graham/Knuth/Patashnik's Concrete Mathematics > (Addison-Wesley 1989). Of course, our library's copy of GKP turned up missing, but someone with a copy gave me the hint: deBruijn sequences. This is great! Not only can I do what I thought impossible, but I have a use for what I thought were useless sequences! For those suffering bibliographic handicaps similar to mine, let me summarize the trick. Suppose we want to draw a Venn diagram showing all Boolean combinations of n sets. Let P(X) be a polynomial of degree n which is irreducible over the field of 2 elements; for example, X^5+X^2+1 works when n=5. Use this to construct a sequence of 0's and 1's by using the corresponding recurrence relation, here a_{i+5} = a_{i+2} + a_i. This sequence cycles after 2^n-1 terms, but has the property that every sequence of length n appears in the cycle except 000...0 . Now construct n convex subsets of the plane as follows: number the vertices of a regular (2^n-1)-gon in order, and let S be the set of those vertices i for which a_i = 1. Let C_0 be the convex hull of that set S, and let C_2, ..., C_{n-1} be obtained by rotating through one vertex at a time. Then vertex i is in a set C_j iff a_{i-j} is in S. In particular, since every sequence of length n appears in S somewhere, it follows that for every subset of the collection of sets C_j there is a vertex lying in precisely that subcollection of C_j's. For visual clarity, the C_j may be replaced by any convex sets containing the same sets of vertices as shown above. Thanks to Chapman for alerting me to the possibility of this construction! Note that this does not address the other question I raised: what is the maximum number of connected components which can be obtained by intersecting k convex subsets in R^n ? (I'm assuming there _is_ a maximum for each k and n, as is the case when n=1.) dave ============================================================================== From: John Rickard Subject: Intersecting convex subsets Date: Fri, 12 Mar 1999 18:57:14 GMT Newsgroups: [missing] To: rusin@vesuvius.math.niu.edu (Dave Rusin) > Note that this does not address the other question I raised: what is the > maximum number of connected components which can be obtained by intersecting > k convex subsets in R^n ? (I'm assuming there _is_ a maximum for each > k and n, as is the case when n=1.) I'm not sure I understand the question; could you state it more precisely? Does considering two congruent concentric regular n-gons in the plane, one rotated with respect to the other, provide an answer? -- John Rickard