edited by
1,384 views
9 votes
9 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?

  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 by

2 Answers

2 votes
2 votes
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 Option $C$ is correct.
edited by
2 votes
2 votes

 

                            L[4]
                             | 
                           L[3]+4 
                            |    
                          L[2]+3     
                           |       
                        L[1]+2       
                         |          
                      L[0]+1           
                       |              
                       1

 

     L[n] = L[n-1]+n
=>        = L[n-2]+(n-1)+n
=>        = L[n-3]+(n-2)+(n-1)+n
=>        = L[n-4]+(n-3)+(n-2)+(n-1)+n
......................................
......................................
......................................
......................................
=>        = L(n-n)+(n-(n-1))+..........+(n-4)+(n-3)+(n-2)+(n-1)+n
=>        = L[0]+1+2+3+4+..........+n    ; Observing carefully the previous line will help you to understand how this(current line) came.
=>        = 1 + n*(n+1)/2                ; we know summation of 1 to n numbers is (n+1)/2\
=>        = 1 + S(n)                     ; where, S(n) = n*(n+1)/2 = 1+2+3+4+..........+n

So, finding 1 + S(n) will let us know the total regions after drawn n lines in a plane.

 

Main Link→ https://sobujerkhuje.wordpress.com/2018/02/09/how-many-regions-do-n-lines-divide-a-plane/

Answer:

Related questions

15 votes
15 votes
4 answers
2
13 votes
13 votes
1 answer
3
Akash Kanase asked Feb 15, 2016
1,300 views
Two points $(4, p)$ and $(0, q)$ lie on a straight line having a slope of $3/4$. The value of $( p – q)$ is$-3$$0$$3$$4$
21 votes
21 votes
2 answers
4
Akash Kanase asked Feb 16, 2016
10,739 views
If $y=5x^2+3$, then the tangent at $x=0$, $y=3$passes through $x=0,y=0$has a slope of $+1$is parallel to the $x$-axishas a slope of $-1$