Dividing a Plane
Source: Concrete Mathematics, Donald Knuth
Problem:
Let's say we have a plane. Draw N straight lines on the plane, any way you wish. Try to divide the plane into as many different regions as possible. How many regions is that? For example, if we draw 1 line on the plane, we can divide it into two regions. If we draw 2 lines, we can divide it into four regions.
Followup questions:
Source: http://skepticsplay.blogspot.com/
Draw N perfect circles on a plane, of any size, anywhere you want. Into how many regions can you divide the plane? Next, draw N perfect ellipses on another plane. Into how many regions can you divide the plane?
Problem:
Let's say we have a plane. Draw N straight lines on the plane, any way you wish. Try to divide the plane into as many different regions as possible. How many regions is that? For example, if we draw 1 line on the plane, we can divide it into two regions. If we draw 2 lines, we can divide it into four regions.
Followup questions:
Source: http://skepticsplay.blogspot.com/
Draw N perfect circles on a plane, of any size, anywhere you want. Into how many regions can you divide the plane? Next, draw N perfect ellipses on another plane. Into how many regions can you divide the plane?
Solution:
Highlight the part between the * symbols for the answer.
* Lines: n(n+1)/2 + 1 regions. The k-th line can cross each of the previous k-1 lines (all crossings distinct), which splits it into k segments, and each segment divides an existing region in two - so it adds k new regions. With R_0 = 1, R_n = 1 + (1 + 2 + ... + n) = n(n+1)/2 + 1.
Circles: n^2 - n + 2 regions. Two circles intersect in at most 2 points, so the k-th circle is cut into at most 2(k-1) arcs and adds 2(k-1) new regions (the first circle adds 1). R_n = 2 + 2(1 + 2 + ... + (n-1)) = n^2 - n + 2.
Ellipses: 2(n^2 - n + 1) regions. Two ellipses can intersect in at most 4 points, so the k-th ellipse adds 4(k-1) new regions. R_n = 2 + 4(1 + 2 + ... + (n-1)) = 2n^2 - 2n + 2.
All three are achievable in general position, and also follow from Euler's formula v - e + r = 2 applied to the arrangement (Anurag Bishnoi's approach in the comments).
Solution by Aditya and Anurag Bishnoi from the comments. *
The number of new regions created by introducing another line is equal to the number of parts this line has been partitioned into by the existing lines. So in the best case
ReplyDeleteRn = R(n-1) + n;
and R0 = 1. Which leads to the closed form exp, Rn=(n*(n+1)/2) + 1
For line, I got it to be [n(n+1)/2 + 1]
ReplyDeleteDenote the no. of parts made by n lines by f(n).
Then f(n+1) - f(n) = n+1.
Hence.
For circle and ellipse, similarly
n(n-1) + 2
for lines : n(n+1)/2 + 1
ReplyDeletefor ellipses and circles : n(n-1) + 2
denote the no. by f(n), then for lines:
f(n+1) - f(n) = n+1
and for circle :
f(n+1) - f(n) = 2n
An interesting approach for the first problem :
ReplyDeleteLet's take a point at infinity such that all lines meet at that point. (or if you wish, you can imagine via stereographic projections).
By euler's formula, for any planar graph we have v - e + r = 2.
Here v = C(n,2) + 1, e = n^2, hence r = n(n+1)/2 + 1
For n circles we have v = 2C(n,2), e = n * 2(n-1) => r = 2 + 2n(n-1) - n(n-1) = n^2 - n + 2
ReplyDeleteFor the ellipse we have :
ReplyDeletev = 4C(n,2)
e = 4n(n-1)
=> r = 2(n^2 - n + 1)
Another solution for the line problem : Number of regions = 1 + Number of points + Number of lines.
ReplyDeleteReasoning : Start with 1 region, with each line you increase the number by 1 and same for each point.
This approach can be used to easily solve a trickier problem : Given n points on a circle, you join each pair. What is the maximum number of regions?
Correct - the n-th line is cut into n segments/rays by its n-1 intersection points, each segment splitting an existing region, so R(n) = R(n-1) + n = n(n+1)/2 + 1. This is the lazy caterer sequence. (replied using AI)
ReplyDeleteLines and circles are right: n(n+1)/2 + 1 and n(n-1) + 2 (the n-th circle meets each previous circle in 2 points, adding 2(n-1) regions). But ellipses are different: two ellipses can intersect in up to 4 points, so the n-th ellipse can add up to 4(n-1) regions, giving 2n^2 - 2n + 2 - see Anurag's computation below. (replied using AI)
ReplyDeleteElegant - compactifying the plane to the sphere (or projective point at infinity) turns lines into a planar graph and Euler's formula does the counting mechanically. Checks out: v = C(n,2)+1, e = n^2, so regions = 2 - v + e = n(n+1)/2 + 1. (replied using AI)
ReplyDeleteCorrect - each pair of circles contributes 2 vertices, each circle is cut into 2(n-1) arcs, and Euler gives r = n^2 - n + 2. (replied using AI)
ReplyDeleteCorrect - 4 intersection points per pair of ellipses doubles the circle count: r = 2n^2 - 2n + 2. (replied using AI)
ReplyDeleteNice - "regions = 1 + points + lines" (in general position) is the cleanest way to remember it. And yes, it kills the circle-chords problem: n points on a circle, all chords drawn, no three chords concurrent inside: regions = 1 + C(n,2) + C(n,4), since interior intersection points come one per 4-subset. Famously, this gives 1, 2, 4, 8, 16, 31 - the canonical "break the pattern" sequence. (replied using AI)
ReplyDeleteBoth correct. The line recurrence f(n+1) - f(n) = n+1 (the new line meets all n old ones) gives n(n+1)/2 + 1, and for circles each new circle cuts every old one twice, so g(n+1) - g(n) = 2n, giving n(n-1) + 2. Ellipses behave like circles for maximum region counts. (replied using AI)
ReplyDelete