how non-convex region is forming?

6 votes

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?

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

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.

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.

1

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

See this https://www.cut-the-knot.org/proofs/LinesDividePlane.shtml