Maximum number of Region created by Lines

Suppose there are N lines in a 2-D space, and you have to maximize the no. of region in which the 2-D space get divided due to the these lines, lets Ln denote the maximum number of region created by n lines.
Is there any closed formula for Ln. ?

E.g, L0 = 1, L1 = 2, L2 = 4

How will the answer change for 3-D space, space being divided into regions by planes rather the lines ?

How will the answer change for N-D space, space being divided into regions by appropriate hyperplanes ?

[2- Dimension]
You can maximize the number of regions of intersection of n lines by making sure that when you draw the ith line you cut all the other i-1 lines at distinct points (not at their points of intersection) thereby increasing the number of regions by magnitude i.

How does the ith line increases the number of regions by i ?`
Convince yourself that on drawing the ith line your line will precisely cut i previously drawn regions, and will cut these i regions into two, thereby increasing the count of number of regions by i.

This algorithm gives the construction of such lines as well.

As far as the formula is concerned it can be solved as:
Li = Li-1 + i
with base case being L0 = 1 (whole space)

Thereby the closed form is : Ln = (n2 + n + 2)/2

1 Like