All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Partitioning Space (Posted on 2004-09-13)
From Pizza Cut, we know the formula for maximum partitioning (pieces) of the circle, given n straight lines (cuts).
______________________________________

1. Determine the maximum number of regions of the plane produced by n intersecting circles.

2. Determine the maximum number of regions of the plane produced by n intersecting ellipses.

3. Determine the maximum number of regions of space produced by n intersecting spheres.

 No Solution Yet Submitted by SilverKnight Rating: 4.5000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Parts 1 and 2 | Comment 2 of 13 |

First, let me ask if the part of the plane NOT bounded by any group of circles is considered a circle. For instance, when there are 0 circles, is there still one region of the plane, or 0 regions? And then when you put the first circle down, now are there two regions of the plane (inside the circle and outside the circle) or just one region?

If we consider the unbounded portion of the plane to be a region, then the answer for the n intersecting circles is n^2-n+2. If the unbounded portion is not a region, then the answer is n^2-n+1.

If we consider the unbounded portion of the plane to be a region, then the answer for the n intersecting ellipses is 2n^2 – 2n + 2. If the unbounded portion is not a region, then the answer is 2n^2 – 2n + 1.

How did I get those? Well, first let’s just say the unbounded portion is NOT a region. I simply found the answer for the first 5 circles or ellipses. And the patterns were this:

Circle:
0                                    0
1                1                  1
2                2                  3
3                4                  7
4                6                13
5                8                21

Notice that for n>2, the number of regions added is 2(n-1). So we just have to sum 2(n-1) from 1 to n, and add one for the first circle for n=1. The sum of 2(n-1) = 2*[the sum of (n-1)] = 2*[(n-1)*n/2] = n(n-1)

So the full formula is n(n-1) + 1 = n^2 – n + 1.
And if we decide that the unbounded area is a region, then we just add one because there will always be one more that we didn’t account for, so n^2 – n + 2.

Ellipses:
0                                     0
1               1                   1
2               4                   5
3               8                 13
4             12                  25
5             16                  41

This time for n>2, the number of regions added is 4(n-1). So now we sum 4(n-1) from 1 to n, and again add one for the first circle for n=1. The sum of 4(n-1) = 4*[the sum of (n-1)] = 4*[(n-1)*n/2] = 2n(n-1).

So the full formula is 2n(n-1) + 1 = 2n^2 – 2n + 1.
And again, if we decide that the unbounded area is a region, then we just add one because there will always be one more that we didn’t account for, so 2n^2 – 2n + 2.

 Posted by nikki on 2004-09-13 15:43:03

 Search: Search body:
Forums (0)