How to divide a plane?

Today, we will continue our journey of implementing recursive solutions and optimizing them based on mathematical induction.

This time, we will focus on a subset of the problem of space partitioning. It is a general idea, where we imagine a multidimensional space and try to divide it into parts by using planes or hyperplanes (higher dimension planes). The thing is to know how many pieces we can create with the given number of dividers. The whole concept is fascinating, but for the sake of our today’s endeavor, we assume that the space to divide is only two-dimensional, which in fact, makes it a plane itself, and the divider is just a one-dimensional plane, thus it is a line.

Dividing a plane

We want to divide a two-dimensional plane into parts using lines. When we have a single line, it is evident that our plane is divided into two separate pieces, one on each side of the given line. When we have two lines that are not parallel, our plane is divided into four parts. That is because our lines have to intersect at one point, and that is the point where all four pieces meet.
What about three lines? How do we put the third line, so that we create as many parts as possible? Well, we can draw it through an already existing intersection point, but in that case, we will end up with only six parts. That is not good enough, and we can do better. When we move our line a little bit, so it intersects the two previous lines at different points, we will get seven parts out of our initial plane. That’s a good deal!

Look at the picture below to see how the plane is divided using one, two, and three lines:

For the sake of consistency, we may add that, when having no lines at our disposal, we end up with one undivided part. That is our base case scenario.

We may define the number of parts P we get by using a certain number of lines n like that: P(n). As we mentioned before:

• P(0) = 1 // zero lines give one undivided part
• P(1) = 2 // one line gives two parts
• P(2) = 4 // two lines give four parts
• P(3) = 7 // three lines give up to seven parts

The question is now, how does it go for higher n, and thus what is the maximal number of parts created by n lines.

Implementation

The goal is to write a little bit of code to calculate P(n). We know for sure the solution for 0, 1, 2, and 3, but what about the next line. How many new parts can we create by adding an additional line to the picture?
The additional line renders the biggest number of new parts when it is not intersecting any of the existing lines at any previous intersection points. It is also true that the more intersections we get, the more parts we create. So, adding the n-th line, we can make it intersect in n-1 new points because we already have n-1 lines lying down. Lines do not have a beginning and an end, so, sooner or later, unparallel lines intersect. As a result, we create n new pieces because our line going through n-1 previous lines is also going through n previous parts, which are now going to be divided in two.

The bottom line is that when adding the n-th line, we can create n new parts. Let’s see the recursive equation:

P(0) = 1
P(n) = P(n-1) + n

When we know that, it is time for a little bit of JavaScript:

let parts = n => n <= 0 ? 1 : parts(n-1) + n;

Optimization

Excellent piece of code! Now, we can easily calculate a further number of parts for a given number of lines. Thus for the number of lines that are: 1, 2, 3, 4, 5, 6, 7, 8, we get the number of pieces that are: 2, 4, 7, 11, 16, 22, 29, 37, respectively.
You may recognize the pattern if you saw it before, but if you didn’t, we may go the other way around.

Let’s try to resolve the recursion:

P(n) =
P(n-1) + n =
P(n-2) + (n+1) + n =
P(n-3) + (n-2) + (n-1) + n = …
P(0) + 1 + 2 + 3 + … + (n-2) + (n-1) + n

We know that P(0) = 1, but what is the sum of every natural number up to n? Let’s call it S(n) because it is a sum. Thus:

P(n) = P(0) + S(n)
S(n) = 1 + 2 + 3 + … + (n-2) + (n-1) + n

We want to find a closed-form expression for our recursive equation. Sometimes, addition is just enough to see the pattern. We will add the two following lines side by side (in columns):

S(n) = 1 + 2 + 3 + … + (n-2) + (n-1) + n // sum this...
S(n) = n + (n-1) + (n-2) + … + 3 + 2 +1 // ... and this

After addition, we get:

2 S(n) = (n+1) + (n+1) + (n+1) + … + (n+1) + (n+1) + (n+1)

How many n+1 do we have on the right side of the equation? Well, exactly n, thus:

2 S(n) = n * (n+ 1)
S(n) = (n * (n+1))/2

Now, we can get back to our P(n) function:

P(n) = P(0) + S(n) = 1 + (n * (n+1))/2

We can use mathematical induction to prove that the statement holds and that this is an equivalent closed-form expression for our recursive equation. We did it in the previous post. I’ll leave it to you, but I will refine our JavaScript code:

let parts = n => 1 + (n * (n+1))/2;

That is a faster version of our previous recursive script.

Conclusion

This geometric puzzle is an excellent example of the power of recursive solutions. Similarly to the previous case of the Tower of Hanoi, we can introduce many variations to the concept of dividing planes into separate parts.
For instance, we can use different shapes than lines, like infinite X shapes, infinite V shapes, or even closed shapes like squares or triangles. The question of adding another element to the existing structure may be highly challenging but also fun, to begin with.
When it is part of the technical interview, remember that the engagement and drive toward the solution are more important than the final result.

When we try to solve any kind of problem of that sort, we may find a recursive pattern and get more information from that. Only when we understand the issue in depth and have some heuristic to calculate the next step can we think about the final optimal solution.

Have a nice day!