TIFR2013-B-9

Question

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?

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

Answer 1

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.

Comments

how non-convex region is forming?

---

I think answer should be C..

---

sorry, my sloppy mistake.
all regions are convex.

Option C is correct.

(edited the answer)

---

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

Please correct me if i am wrong.

 

---

@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