231 views

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 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?

1. $O (n)$ regions are produced, and each region is convex.
2. $O (n^{2})$ regions are produced but they need not all be convex.
3. $O (n^{2})$ regions are produced, and each region is convex.
4. $O (n \log n)$ regions are produced, but they need not all be convex.
5. All regions are convex but there may be exponentially many of them.

edited | 231 views

+1 vote
Option C must be correct.

Regions divided by n lines = 1+1+2+3+4+..........+n-1 = 1 + n(n-1)/2 = O(n^2)

option B can be easily discarded as convex segments are obvious.

Hence C is correct.
by (141 points)
edited
0
how non-convex region is forming?
0

I think answer should be C..

0
sorry, my sloppy mistake.
all regions are convex.

Option C is correct.

0

No-convex regions are possible, isn't it?

Please correct me if i am wrong.

0

@Nitesh Tripathi I think region divided by n lines should be ---. n ( n + 1 ) / 2 + 1