Number of regions formed by $m$ circles and $n$ straight lines

Question

Suppose there are $m$ circles and $n$ straight lines in the plane. Find the maximum number of regions formed by them.

I think that the question is self-explanatory, otherwise, I'll explain it clearly.

The following link might be helpful for an idea but I don't think that it's something extremely helpful (I want something rigorous). I think we can use induction but that's only possible if we can draw the circles and lines in a desired pattern. The way in which the circles and lines have been presented in the link isn't exactly how we can think for $m$ circles and $n$ lines.

Answer 1

The general idea is as follows: You start with an original configuration of some elements (an element being a line or a circle) already in the plane, then add a new element (line or circle) to get a new configuration. The existing regions in the original configuration subdivide the new element into certain sections.

The important part is that these sections on the new element determine by how much the number of regions increases. Because each section subdivides a region from the original configurations into 2 regions of the new configuration, the number of regions increases by exactly the amount of sections that the original regions create from the new element.

OTOH, the number of those sections is easily determined by the number of common points the new element has with the elements of the original configuration.

If the new element is a line that has $l$ common points with the original configuration, then the new line will be divided into $l+1$ sections.

If the new element is a circle that has $c$ common points with the original configuration, then the new circle will be divided into $c$ sections if $c > 0$, or 1 section if $c=0$.

Let's call $R(m,n)$ the maximum amount of regions that $m$ circles and $n$ lines can divide the plane into.

We start with $R(0,0)=1$: The whole plane is one region. $R(1,0)=2$, because a single circle has an outer and an inner region.

For $m \ge 2$ we get $R(m,0) \le R(m-1,0) + 2(m-1)$. That's because the $m-1$ existing circles can have at most 2 common points with the new circle each (and $2(m-1) \ge 1$ in case the new circle has no point in common with existing circles).

This leads, per induction, to $R(m,0) \le m(m-1)+2$ for $m \ge 1$, a formula that (with equality) is also in the linked treaty. In order to have 'common' estimation also for $m=0$, let's define $s(m)=1$ for $m=0$ and $s(m)=2$ for $m > 1$. Thus we get $R(m,0) \le m(m-1)+s(m)$ for $m \ge 0$.

Now we do the same thing, increasing the number of lines step by step. If we add a line to an original configuration with $m$ circles and $n-1$ lines, then that new line has at most $2m$ common points with all the $m$ circles and at most $n-1$ common points with the other $n-1$ lines.

Thus we get $R(m,n) \le R(m,n-1) + (2m + n-1) + 1$.

Again, by induction over $n$, this leads to $R(m,n) \le R(m,0) + 2mn + \frac{n(n+1)}{2} = m(m-1) + s(m) + 2mn + \frac{n(n+1)}{2}$.

Now I claim that the inequality is really an equality.

Obviously, any configuration of $m$ circles and $n$ lines can be obtained by starting with the empty plane and first adding circles, one by one and then adding lines, one by one. In each step, if the used bound on $R(m,0)$ and $R(m,n)$, resp., is sharp, depends on exactly 2 things:

A) That the number of common points between the new element and the old elements is really the maximum value (1 for a line intersectiong another line, 2 for a circle intersecting another circle or line), and

B) that those common point are all different.

So in order prove the equality, we need to construct $m$ circles and $n$ lines that fullfill A) and B).

Select a point M in the plane. Choose $m$ different circles with radius equal to 1 in the plane, whose midpoints have distance at most $\frac13$ to M. These circles

1) all intersect in 2 points, and

2) all contain M as an inner point.

1) makes A) true for the circles. It should also be easy to see B) can be fullfilled, as the set from which midpoints can be chosen is a 2-dimensional object (a filled circle), while the condition that a new circle should not go through an existing intersection point excludes only a 1-dimensional set of points.

2) makes sure that :

3) we have a small circle $C$ with some radius $\epsilon >0$ around M that is inside all the circles.

Take any set of $n$ lines in general position (no 2 parallel, no 3 intersecting in 1 point). Apply a centric compression to the lines such that all the intersections are inside a circle of radius $\epsilon$. Now translate the compressed lines such that all the intersections are inside the circle $C$.

This means all the intersections between the lines are different from all the intersections between the circles. In addition, each line contains a point (any of it inisde $C$) that is inside each circle (see 3) above), so each line will intersect with each circle in exactly 2 points.

What needs to be proven to verify condition B) above is that those line vs. circle intersections are all different from the existing circle vs. circle intersections. They might not actually be, but we have one more degree of freedom to exploit: If we rotate the configuration of lines around M, all their intersections stay inside $C$. But only a finite number of rotation angles create invalid configurations where a line vs. circle intersection is equal to an existing circle vs. circle intersections, so one rotation angle can be found where this is not the case and condition B) is fullfilled.

This means we can find a configuration where all the lines and circles intersect in the maximum number of ways in all different points, so in the estimations for $R(m,n)$ we would always get equality in each step.

This concludes the proof that

$$R(m,n) = m(m-1) + s(m) + 2mn + \frac{n(n+1)}{2}$$

where $s(m)=1$ for $m=0$ and $s(m)=2$ for $m \ge 1$.

Answer 2

Recall the Euler characteristic of the plane is $1$. For any dissection of the plane by circles and lines into $V$ vertices, $E$ edges and $F$ faces/regions (bounded and unbounded combined), we have

$$V - E + F = 1\quad\iff\quad F = E - V + 1$$

Maximizing $F$ is equivalent to maximize the difference $E - V$.

Let $F_{mn}$ be the maximum number of regions we can achieve with $m$ circles and $n$ lines.

Let us consider the case $n = 0$ first. It is easy to see

$$F_{00} = 1\quad\text{ and }\quad F_{10} = 2\tag{*1a}$$

For $m \ge 2$, consider what happens when we add the $k^{th}$ circle ($k \le 2 \le m$).

It either doesn't intersect with any of the previous $k-1$ circles. In this case, $E$ increases by one, $V$ by none and $F$ increases by only one.

Otherwise, the $k^{th}$ circle intersect with $1 \le p \le k-1$ circles and make at most $q \le 2p$ distinct intersections. Independent of the locations of these intersections, the $k^{th}$ circle split into equal numbers of vertices and edges, It will not contribute anything to the difference $E-V$.

However, the $q$ intersections can split at most $q$ old edges on the first $k-1$ circles. This increase $E$ by at most $q \le 2p \le 2(k-1)$. From this, we can conclude

$$F_{k0} \le F_{k-1,0} + 2(k-1)\tag{*1b}$$

Combine $(*1a)$ and $(*1b)$ for $k = 2,\ldots, m$ , we obtain

$$F_{m0} \le 2 + \sum_{k=2}^m 2(k-1) = m(m-1) + 2\quad\text{ for }\quad m \ge 2$$

To see this is actually an equality. It suffices to find a configuration of $m$ circles where every pair of circles intersect with each other and all the intersections are disjoint. A simple way is start from $m$ unit circles centered at origin and then move the $k^{th}$ circle along the direction $\left(\cos\frac{2\pi k}{m},\sin\frac{2\pi k}{m}\right)$ for a common same amount.

To summarize, when $n = 0$, we have

$$F_{m0} = \begin{cases}1, & m = 0\\ m(m-1) + 2& m > 0\end{cases}\tag{*1}$$

Let us switch to the case $n > 0$. Consider what happens when we add the $k$ line ($ 1 \le k \le n$).

It can make at most $2m$ intersections with the circles and $k-1$ intersection with the previous $k-1$ lines. Independent of the locations of the intersections, the vertices and edges on the $k^{th}$ line with contribute one to $E - V$. Since these intersections can split at most $2m + k - 1$ old edges on the $m$ circles and first $k-1$ lines, we obtain

$$F_{mk} \le F_{m,k-1} + (2m+k)\tag{*2a}$$

Combine $(*1)$ with $(*2a)$ for $k = 1,\ldots, n$, we obtain

$$F_{mn} \le F_{m0} + \sum_{k=1}^n(2m+k) = F_{m0} +2mn + \frac{n(n+1)}{2}\tag{*2b}$$

To see this is actually an equality. It suffices to find a configuration where all combinations of circles and lines intersect with each other and all the intersections are disjoint. Choose the $m$ circles as before. For the $n$ lines, choose $n$ distinct directions from $\bigcup\limits_{k=0}^{m-1} \left( \frac{\pi(k+1-\epsilon)}{m},\frac{\pi(k+\epsilon)}{m}\right)$ and for each direction, construct a line along that direction through origin. This will ensure all lines and circles intersect each other. Furthermore, the line-circle and circle-circle intersections are all disjoint. The only trouble remain is all line-line intersection occur at the origin! Parallel shift each lines for a small amount can make all line-line intersections disjoint (this is always possible because in each move, there is a finite number of amounts to avoid but infinitely many small amounts to pick).

In general, we have established $$ F_{mn} = \begin{cases} \frac{n(n+1)}{2} + 1, & m = 0\\ m(m-1) + 2 + 2mn + \frac{n(n+1)}{2},&m > 0 \end{cases} $$