The Gateway to Computer Science Excellence
+5 votes
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.
in Numerical Ability by Boss (30.8k points)
edited by | 231 views

1 Answer

+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 by
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.

(edited the answer)
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

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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,315 answers
198,359 comments
105,087 users