Partition of the plane by lines

It’s an exercise in induction to prove that n lines in general position divide the plane into latex M_n=n(n+1)/2+1 regions, and this number of regions is the maximal possible. Here is a partition that realizes M_3:

Three lines in general position

Three lines can also divide the plane into 6 regions instead of 7: this happens if the triangle collapses to a point, or if two of the lines are made parallel. However, 3 lines can never divide the plane into 5 regions.

Define \mu_n to be the smallest integer such that for any integer m\in [\mu_n, M_n] there is a partition of the plane into m regions by n lines. So, \mu_3=6, and of course \mu_2=3 and \mu_1=M_1=2. Here are a few more values of \mu_n, with examples in lieu of proofs.

Can't reduce the number of regions by one.
Still can't reduce the number of regions by one.

The last one, unattainability of 23 with 8 lines, isn’t easy to prove.

Does \mu_n have a closed form? 2,3,6,8,12,15,18,24 is not in OEIS, unlike the upper bound.

Update: the 1993 paper Classification of arrangements by the number of their cells by Nicola Martinov gives a complete description of the pairs (n,f) for which there is a partition of (projective) plane by n lines into f regions. In the affine version considered above we should simply says that the ideal line is also a part of arrangement; thus, 3-line affine arrangements correspond to 4-line projective arrangements, etc. However, it is not entirely trivial to get \mu_n out of Martinov’s formulas.

Leave a Reply


You are commenting using your account. Log Out /  Change )

Google+ photo


Twitter picture


Facebook photo


Connecting to %s