Regions with polygons

[littlemathquark]

Homework Statement

At most, into how many regions can 𝑘 convex polygons divide a plane?

Relevant Equations

At most, into how many regions can 𝑘 convex polygons divide a plane?

One triangle divide plane 2 region, 2 triangle divide plane at most 8 region (maximum number of intersection points+2=6+2). One quadrilateral divide plane 2 region, 2 quadrilateral divide plane at most 10 region. (maximum number of intersection points+2=8+2).
So k convex n-polygon(n-gon) can divide plane $2nC(k,2)+2$ regions, but I'm not sure. I have no proof.

 

[anuttarasammyak]

I can not read your $2nC(k,2)$. Is C combination ?

 

[littlemathquark]

Yes, $C(k,2)$ is combination. More clear $(2\times n\times C(k,2))+2$

 

[littlemathquark]

I think each intersection point increases the number of regions by 1.

 

[anuttarasammyak]

Thanks. k=0 seems not included in your formula.

 

[littlemathquark]

Yes, also $k=1$ seems not included in formula. For $k=0$ number of region is 1 region (plane itself), for $k=1$ number of region is 2( in and out of polygon).

 

[littlemathquark]

I think it can be used Euler formula (V-E+F=2) but I can't manage it for now.

 

[littlemathquark]

Consider two k -gons, A and B . Since we are talking about convex polygons, each edge of A can at most cut B at two points, with one point entering the polygon and with the other exiting. Thus, we will have a total of 2k intersection points. Now consider the planar graph of the vertices of the two k -gons and these 2k intersection points. Originally, there were k edges in each of the k -gons (total 2k ). Each new intersection point splits two of the participating edges into two parts, thus introducing two new edges. Thus, |V|=k+k+2k=4k and |E|=k+k+2×2k=6k
Using Euler's formula, |V|−|E|+|F|=2, we have |F|=6k−4k+2=2k+2

But I can't generalize this for n number of k-gons.

 

[littlemathquark]

I think I can generalize:

Let's first consider 2 k-gons. We can observe that each side of these k-gons intersects each side of the other k-gon at most 2 points (when entering and exiting the interior region of the convex polygon). Accordingly, the total number of intersection points should be 2k. Now, if we take n k-gons, the total number of intersection points will be 2k * C(n, 2) = kn(n-1). These intersection points mean new vertex points for the resulting planar graph. So, while there were a total of nk vertices initially, the total number of vertices becomes V = nk + kn(n-1) as a result of the intersection of the polygons. Here, an important observation is that each intersection point adds 2 new edges to the graph. In this case, while there were nk edges initially, the number of edges in the final state should be E = nk + 2 * kn(n-1). Now, if we run the Euler formula, the number of regions formed is found as follows:

V - E + F = 2nk + kn(n-1) - nk - 2kn(n-1) + F = 2F = 2 + kn(n-1) = 2 + 2k * C(n, 2)

 

[fresh_42]

I have a few remarks that are not actually on topic. Geometry questions are hard to describe, to discuss, or to solve on the internet. It's an occasion where a blackboard is really missing. Questions like this are often first translated into a dual form, e.g. edges are converted to vertices and vice versa, or some algebraic tools are implemented. The crucial point here seems to me to be the step from k to k+1 polygons. How many of the previous regions can maximally be intersected by another polygon? You have too many free parameters. Not only k and n but also the angle of rotation and the side lengths. And convex doesn't mean regular, which makes it even more variable. Maybe you can get an idea by starting with ellipses.

 

[littlemathquark]

Thank you, I think about circles and ellipses.

Here another solution: ( it's changed k and n)

First, two convex n-gons with no overlapping sides can intersect at most 2n points (this occurs when each side has a vertex opposite it). Let's define a function F(n, k) that represents the maximum number of regions a plane can be divided into by k n-gons.

Assuming we know F(n, m), let's consider F(n, m+1). The (m+1)th n-gon can intersect all the preceding n-gons in at most 2nm points. Each intersection point increases the number of regions by one, as the n-gon cuts through existing regions. Thus:

F(n, m+1) = F(n, m) + 2nm

and

F(n, 2) - F(n, 1) = 2n⋅1
F(n, 3) - F(n, 2) = 2n⋅2...
.....
F(n, k) - F(n, k-1) = 2n⋅(k-1)

From the telescoping sum (and since F(n, 1) = 2), we derive F(n, k) = nk(k-1) + 2.

 

[littlemathquark]

I think I can generalize:

Let's first consider 2 k-gons. We can observe that each side of these k-gons intersects each side of the other k-gon at most 2 points (when entering and exiting the interior region of the convex polygon). Accordingly, the total number of intersection points should be 2k. Now, if we take n k-gons, the total number of intersection points will be 2k * C(n, 2) = kn(n-1). These intersection points mean new vertex points for the resulting planar graph. So, while there were a total of nk vertices initially, the total number of vertices becomes V = nk + kn(n-1) as a result of the intersection of the polygons. Here, an important observation is that each intersection point adds 2 new edges to the graph. In this case, while there were nk edges initially, the number of edges in the final state should be E = nk + 2 * kn(n-1). Now, if we run the Euler formula, the number of regions formed is found as follows:

V - E + F = 2nk + kn(n-1) - nk - 2kn(n-1) + F = 2F = 2 + kn(n-1) = 2 + 2k * C(n, 2)

İn solution, I can not answer that question:
If we cannot ideally create the intersection points and fail to achieve this upper bound, how do we show that the upper bound will still hold?

 

[fresh_42]

Any upper bound is easy. Every single line divides the plane into a left and a right. Hence $2^k$ where $k$ is the number of lines is a trivial upper bound. We cannot have more regions. But this is likely by far too large.