Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In this post it is mentioned that $n$ straight lines can divide the plane into a maximum number of $(n^{2}+n+2)/2$ different regions.

What happens if we use circles instead of lines? That is, what is the maximum number of regions into which n circles can divide the plane?

After some exploration it seems to me that in order to get maximum division the circles must intersect pairwise, with no two of them tangent, none of them being inside another and no three of them concurrent (That is no three intersecting at a point).

The answer seems to me to be affirmative, as the number I obtain is $n^{2}-n+2$ different regions. Is that correct?

share|improve this question
add comment

4 Answers

For the question stated in the title, the answer is yes, if more is interpreted as "more than or equal to" (aka. "in the French sense").

Proof: let $\Lambda$ be a collection of lines, and let $P$ be the extended two plane (the Riemann sphere). Let $P_1$ be a connected component of $P\setminus \Lambda$. Let $C$ be a small circle entirely contained in $P_1$. Let $\Phi$ be the conformal inversion of $P$ about $C$. Then by elementary properties of conformal inversion, $\Phi(\Lambda)$ is now a collection of circles in $P$. The number of connected components of $P\setminus \Phi(\Lambda)$ is the same as the number of connected components of $P\setminus \Lambda$ since $\Phi$ is continuous. So this shows that for any collection of lines, one can find a collection of circles that divides the plane into at least the same number of regions.

Remark: via the conformal inversion, all the circles in $\Phi(\Lambda)$ thus constructed pass through the center of the circle $C$. One can imagine that by perturbing one of the circles somewhat to reduce concurrency, one can increase the number of regions.


Another way to think about it is that lines can be approximated by really, really large circles. So starting with a configuration of lines, you can replace the lines with really really large circles. Then in the finite region "close" to where all the intersections are, the number of regions formed is already the same as that coming from lines. But when the circles "curve back", additional intersections can happen and that can only introduce "new" regions.


Lastly, yes, the number you derived is correct. See also this OEIS entry.

share|improve this answer
1  
I like your answer, as it is very conceptual. I deduced the formula inductively, as I sketch in my answer below. –  John Sep 4 '12 at 12:22
    
Nice answer +1, I had somewhat the same idea but lacked the knowledge in this area to write a solution. I was hoping for someone to write something like this. –  Simon Markett Sep 4 '12 at 13:15
4  
+1 for the conceptual explanation in the 4th paragraph. –  Dan Neely Sep 4 '12 at 14:33
1  
-1 for "in the french sense" –  Yuck Sep 4 '12 at 16:47
1  
@LarsH: in French, a nombre positif is what we conventionally in English call a "nonnegative number". In general in French mathematics texts the phrase "est supérieur à" is synonymous to the English "is greater or equal to". What in English is "is greater than" would need to be qualified in French as "est supérieur strictement à" (literally: "strictly greater than"). It is a historical/cultural/conventional thing. –  Willie Wong Sep 5 '12 at 10:32
show 3 more comments
up vote 10 down vote accepted

One may deduce the formula $n^{2}-n+2$ as follows: Start with $m$ circles already drawn on the plane with no two of them tangent, none of them being inside another and no three of them concurrent. Then draw the $m+1$ circle $C$ so that is does not violate the propeties stated before and see how it helps increase the number of regions. Indeed, we can see that that $C$ intersects each of the remaining $m$ circles at two points. Therefore, $C$ is divided into $2m$ arcs, each of which divides in two a region formed previously by the first $m$ circles. But a circle divides the plane into two regions, and so we can count step by step ($m=1,2,\cdots, n$) the total number of regions obatined after drawing the $n$-th circle. That is, $$ 2+2(2-1)+2(3-1)+2(4-1)+\cdots+2(n-1)=n^{2}-n+2 $$

Since $n^{2}-n+2\ge (n^{2}+n+2)/2$ for $n\ge 1$ the answer is affirmative.

ADDENDUM: An easy way to see that the answer to my question is affirmative without finding a formula may be as follows: Suppose that $l_{n}$ is the maximum number of regions into which the plane $\mathbb{R}^{2}$ can be divided by $n$ lines, and that $c_{n}$ is the maximum number of regions into which the plane can be divided by $n$ circles.

Now, in the one-point compactification $\mathbb{R}^{2}\cup\{\infty\}$ of the plane, denoted by $S$ (a sphere), the $n$ lines become circles intersecting all at the point $\infty$. Therefore, these circles divide $S$ into at least $l_{n}$ regions. Now, if we pick a point $p$ in the complement in $S$ of the circles and take the stereographic projection through $p$ mapping onto the plane tangent to $S$ at the antipode of $p$ we obtain a plane which is divided by $n$ circles into at least $l_{n}$ regions. Therefore, $l_{n}\le c_{n}$.

Moreover, from this we can see that the plane and the sphere have equal maximum number of regions into which they can be divided by circles.

share|improve this answer
add comment

A qualitative approach:

Consider a group of $n$ lines that divide the plane into maximally many regions. The intersections between the lines all fall within a bounded area of the plane. Now replaces each of the lines with a huge circle, so large that within the bounded area-of-intersections it deviates from a straight line by much less than the distance between two points of intersection.

Then you still have all the regions you had with lines. However, if there are at least three circles, you also get some new regions that are far away from the central bounded area.

share|improve this answer
    
I think this approach (and that of @Wille Wong, but it has so many comments) can be complemented by a heuristic argument as to why the "some new regions" far away in fact almost double the number of regions. Inversion in a very lagre circle centered near the intersections of the lines, therefore intersecting the lines almost perpendicularly, maps lines to "nearby" circles while interchanging regions inside and outside. But it deforms $n$ outside regions to the number $f(n)$ of inside regions, adding $f(n)-n$ outside regions. So one expects $2f(n)-n$ regions for circles, $f(n)=\frac{n^2+n+2}2$. –  Marc van Leeuwen Sep 5 '12 at 12:56
add comment

By a simple induction one shows that if every pair among $n$ circles intersects each other transversally, without any three circles ever being concurrent, then they divide the plain into $$1+1+2+4+6+\cdots+2(n-1)=1+[n>0]+\sum_{i=1}^{n-1}2i=1+[n>0]+n(n-1) $$ different regions; this is indeed equal to the formula $n^2-n+2$ you guessed, except for $n=0$ where it (correctly) gives $1$ rather than $2$. Indeed for $n=0$ one has a single region, adding a first circle adds one region, and every next circle number $i$ cuts each of the previous $i-1$ circles twice, so it has $2(i-1)$ points of intesection, and between those points it passes through $2(i-1)$ previous regions, each of which it cuts into $2$ regions, adding $2(i-1)$ regions to the total.

By constrast, working with lines instead of circles, every line after the first intersects previous lines only once, plus a passage at infinity, so that line number $i$ adds $i$ new regions. This is weakly less than the $2(i-1)$ regions added in the circle case, and strictly less for $i\geq3$. which explains the inequality you asked about.

It is easy to see that the transversal intesection property can indeed be attained: just take all circles the same radius $r$ and fix one point $P$ that is to lie in the interior of all circles (their centers lie in the interior $D$ of the disk around $P$ with radius $r$). Also, given a finite set of circles, the set of points that is excluded as center of the $n$-the circle because of the "no concurrence" condition is the union of a finite number of circles, which does not exhaust $D$, so it is always possible to choose a next circle satisfying the given conditions. (For the "union of circles" claim, observe that three such circles are concurrent if and only if their centers lie on a circle of radius $r$.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.