3
$\begingroup$

Given $n$ circles of possibly different radii, how many distinct regions can there be? For small $n$, I can work it out with pictures. (I'm pretty sure $n=4$ can yield 13 distinct regions, but not positive.)

Just curious what an approach to the problem could be.

E.g. I have considered that is could be a quadratic sequence based on skimpy evidence, but don't know why that would be, or how to prove it.

I would also be interested to know if there was a way of doing this problem with regular $n$-gons. (I am assuming that there would be more regions, but am not sure.)

  • 0
    With two n-gons you can get $2n+1$ regions by having the centers match and clocking one by $\frac{\pi}{n}$2011-05-18
  • 0
    I understand, but as you get more I think (but am not sure) you can do better by varying the size of the n-gons2011-05-18
  • 0
    I don't think you can do better for only 2. You want to maximize the number of intersection points. This approach generalizes to $mn+1$ for $m$ n-gons, but eventually a quadratic approach will dominate.2011-05-18
  • 0
    But for more than 2?2011-05-18
  • 0
    For more than 2, the proof for circles goes through. Note I left out the exterior above, so two n-gons can give $2n+2$. Two n-gons can intersect in $2n$ points, so if you have $m$ already, the $m+1^{\text{st}}$ can intersect in $2mn$ points, adding $2mn$ regions. In total, for $m$ n-gons, we get $2+m(m-1)n$ regions, where for circles $n=1$ instead of $\infty$.2011-05-18

2 Answers 2

5

OEIS gives the number of regions for circles. It gets 14 for 4 circles, including the exterior. The general formula is $n^2-n+2$. Allowing different size circles doesn't help. The proof is by induction. With one circle there are $2$ regions. Assuming the formula is true for $n$, the new circle can cross old ones in at most $2n$ points. Each segment can cut an existing region in two parts, adding $2n$ regions. So the maximum number of regions for $n+1$ circles is $n^2-n+2+2n=(n+1)^2-(n+1)+2$

  • 0
    Exterior meaning the space occupied for no circles? You might want to edit your post to include the formula... In addition, does this mean any sized circles, or all the same size?2011-05-18
  • 0
    @soandos: Yes, "exterior" does mean the space occupied by no circles, so your "13" is correct. Also, as the OEIS entry makes no mention of the size of the circles, I think it's any sized circles.2011-05-18
  • 0
    Do you know why this formula works?2011-05-18
  • 0
    @Ross: Change to reflect necod's comment (listed as answer as he does not have enough rep)2011-05-18
  • 0
    @soandos: Note that Ross's solution is correct for **$n$** circles in a plane; OEIS lists $n^2 + n +2$ as the maximum number of regions created by **$(n+1)$** circles (which Ross computes in his proof by induction, with result matching OEIS result for $n + 1$ circles. See http://oeis.org/A002061 for the formula for n such circles (given by Ross).2011-05-18
  • 0
    @Amy: thank you for explaining2011-05-18
  • 0
    @soandos: Generally speaking, the person posting a question should "accept" an answer if it is helpful and sufficient (or, in the case where more than one answer is provided, then the answer that is most helpful should be accepted, provided there is a helpful answer, of course!)2011-05-18
  • 0
    @Amy, apologies, this post was accepted as the answer until the post below pointed something out. Forgot to re-accept. Thank you for the reminder.2011-05-18
  • 0
    Not a problem! I'm sorry if I came across as scolding...I certainly didn't intend to...I just "look out for others" - in terms of acceptance of answers (I'd do the same for my own posted answers, when it's clear it helped, but that would be "tooting my own horn"...2011-05-18
2

The source quoted by Ross Millikan (OEIS) gives different formula:

$$n^2+n+2$$

  • 2
    That is off by 1 from what you would think, as stated in the OEIS notes. 1 circle gives 2 regions, not 4. I changed the sign of the middle term to minus to account for that in my proof.2011-05-18
  • 0
    @Ross, @necod: please see my comment above this answer for more details.2011-05-18