TIFR CSE 2013 | Part B | Question: 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

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.

Comments

@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

---

how all the regions are convex,i think non convex regions are also possible

---

@jaco

Straight lines extend to infinity in both directions. Also given in the question, no two lines are parallel. Yet you have taken two parallel vertical lines. I have corrected the line colored in blue. You can see that all regions are convex.

And the number of regions in the link given by @Gyanu is correct. We can verify it.

As we have 5 lines and they are placed appropriately to get the maximum number of regions.

Therefore, Maximum number of regions is:

$L_{n} = \frac{n(n+1)}{2} + 1 = \frac{5(5+1)}{2} + 1 = 16$

And indeed we have 16 regions in the figure.

The formula given in the question is wrong. Please edit it, @Arjun sir.

Anyway, Option C) is correct as $L_{n} = O(n^{2})$.

Answer 2

 

                            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/