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  <rchapman@mpce.mq.edu.au> 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 <jrr@virata.com>
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