How Many Regions and Convexity with n Straight Lines on a Plane?

[matrixone]

Homework Statement

Suppose n straight lines are drawn on a plane. When these lines are removed, the plane falls apart into several connected components called regions.A region R is is said to be convex if it has the following property: whenever two points are in R, then the entire line segment joining them is in R.Suppose no two of the n lines are parallel. Which of the following is true?
A) O(n) regions are produced, and each region is convex.
B) O(n²) regions are produced but they need not all be convex.
C) O(n²) regions are produced, and each region is convex.
D) O(nlogn) regions are produced, but they need not all be convex.
E) All regions are convex but there may be exponentially many of them.

Homework Equations

The Attempt at a Solution

Someone please explain what we have to start with , i.e what is there in the plane before those straight lines ?

 

[mfb]

Someone please explain what we have to start with , i.e what is there in the plane before those straight lines ?

There is nothing in the plane.

Here is an example of the plane with two lines (imagine the lines being extended to infinity)

How many different regions do you find?

 

[matrixone]

There is nothing in the plane.

Here is an example of the plane with two lines (imagine the lines being extended to infinity)

How many different regions do you find?

I find 4 regions. Sir, but it is mentioned that the regions are formed after removing the lines. This is what confuses me. and the region have "connected components" what is there to connect if the lines are gone ?

 

[Mark44]

When these lines are removed, the plane falls apart into several connected components called regions.

I don't understand this either. I read the first part, "When these lines are removed," to mean that the lines are like cutting a piece of paper with a pair of scissors. If the cuts are parallel, the paper is divided into three pieces. If the cuts are not parallel, you get four pieces. (I'm assuming that paper is large enough to include the point of intersection of the two lines/cuts.)

The part about the parts being "connected components" is unclear. I believe what the write is trying to convey is that each piece is connected to itself, with no region consisting of two unconnected parts. I don't see how any piece could be connected to any other.

 

[mfb]

The set of all points of the plane minus the points of the lines has different regions - four in the example above.
"Connected" refers to the points within such a region, not between regions.

The phrasing is a bit odd.

 

[matrixone]

The set of all points of the plane minus the points of the lines has different regions - four in the example above.
"Connected" refers to the points within such a region, not between regions.

The phrasing is a bit odd.

Since the lines need not be of finite length, above figure is possible. there are 7 lines and 2 regions here. But the inner region is not convex as per the red points.
So this proves there can be non convex regionsOr is it that "line" means infinite length and "line segment" means finite ?
In that case i don't think there any way to have non convex regions Now the question is to find the max number of regions that can be formed with n lines(with no two lines parallel).
Can you give a start ?
I have some ideas like , at the max a new line is going to multiply the number of regions by two , (but i don't see this happening except for n=2)
and if all lines are intersected at a point, then number of regions will be twice the number of lines.

But i can't move any further :(

 

[Dick]

Since the lines need not be of finite length, above figure is possible. there are 7 lines and 2 regions here. But the inner region is not convex as per the red points.
So this proves there can be non convex regionsOr is it that "line" means infinite length and "line segment" means finite ?
In that case i don't think there any way to have non convex regionsNow the question is to find the max number of regions that can be formed with n lines(with no two lines parallel).
Can you give a start ?
I have some ideas like , at the max a new line is going to multiply the number of regions by two , (but i don't see this happening except for n=2)
and if all lines are intersected at a point, then number of regions will be twice the number of lines.

But i can't move any further :(

If you assume no that you never have more than two lines intersecting at any given point you should be able to find a simple pattern describing the number of regions. Think about what happens when you add one more line to an existing set of regions.

 

[mfb]

I'm quite sure the lines do not have end, otherwise the problem is ill-defined.

and if all lines are intersected at a point

That won't happen in general, but the possibility of that doesn't change the answer.

 

[mjc123]

OK, let's see. No lines, one region. One line, two regions. Two lines, four regions. Three lines, seven regions (unless they all pass hrough the same point, giving one "region" of zero area). Now if you have n infinite non-parallel lines, the n+1th line will cross each of these lines (passing from one region to another) once, i.e. it passes through n+1 regions, dividing each in two. Therefore the number of regions N(n+1) = N(n) + n+1. Looking at the first few values we see that N(n) = n(n+1)/2 + 1. Thus N(n) is O(n²) (I think; I have just looked up Big O Notation, never having heard of it before). It seems to me they must all be convex, but I don't know that I could prove it. I suppose if you had a concave region as in the diagram above, those two lines must extend beyond their point of meeting to intersect other lines, and that "region" would be divided into multiple convex regions.

 

[mfb]

Right.

For a more formal proof that the regions have to be convex: Assume they are not. Then there are two points A,B in a region where some point between them has to be a border of the region, i. e. part one of the n lines. You can show that this implies that A and B cannot be in the same region.

 

[matrixone]

I'm quite sure the lines do not have end, otherwise the problem is ill-defined.
That won't happen in general, but the possibility of that doesn't change the answer.

Ya. Because the Big O notation considers the worst case scenario. Right ?

OK, let's see. No lines, one region. One line, two regions. Two lines, four regions. Three lines, seven regions (unless they all pass hrough the same point, giving one "region" of zero area). Now if you have n infinite non-parallel lines, the n+1th line will cross each of these lines (passing from one region to another) once, i.e. it passes through n+1 regions, dividing each in two. Therefore the number of regions N(n+1) = N(n) + n+1. Looking at the first few values we see that N(n) = n(n+1)/2 + 1. Thus N(n) is O(n²) (I think; I have just looked up Big O Notation, never having heard of it before). It seems to me they must all be convex, but I don't know that I could prove it. I suppose if you had a concave region as in the diagram above, those two lines must extend beyond their point of meeting to intersect other lines, and that "region" would be divided into multiple convex regions.

Awesome! . Now i got it. Thanks. :)

Right.

For a more formal proof that the regions have to be convex: Assume they are not. Then there are two points A,B in a region where some point between them has to be a border of the region, i. e. part one of the n lines. You can show that this implies that A and B cannot be in the same region.

border of the region which is a line is boundless and that prevents A and B to be in the same region. Right ?
Thanks a lot Sir :)
I think i got it now :)

 

[mfb]

Ya. Because the Big O notation considers the worst case scenario. Right ?

Right.

border of the region which is a line is boundless and that prevents A and B to be in the same region. Right ?

Right.