One line divides the plane into two halves or regions, while two lines divide the plane...

Transcribed Image Text:

One line divides the plane into two halves or regions, while two lines divide the plane into four regions. In this problem we study the number of regions in which n lines divide the plane. For simplicity, assume that no three lines intersect at a given point and that no two lines are parallel to one another. Here is a picture of the 7 regions defined by 3 lines. 5 4 2 3 1 7 6 Consider the following algorithm that builds the set of regions by starting from a single region encompassing the whole plane, and iteratively refines the set of regions by processing one line at a time. Activate 1: function BUILD ARRANGEMENT (lines) [new region spanning whole plane] lines do for region regions do if line intersects region then Append region to old 2: 3: regions for line 4: old[] 5: new [] 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: return regions left, right split region through line Append left to new Append right to new for xold do Remove x from regions for x = new do Append x to regions a) Prove that at the beginning of the ith iteration of the for loop in Line 3 the line cuts through exactly i regions from the previous iteration. b) Prove that at the end of the ith iteration of the for loop in Line 3 2+1+2 regions. Remember to use the fact that no three lines intersect in the same point! we have One line divides the plane into two halves or regions, while two lines divide the plane into four regions. In this problem we study the number of regions in which n lines divide the plane. For simplicity, assume that no three lines intersect at a given point and that no two lines are parallel to one another. Here is a picture of the 7 regions defined by 3 lines. 5 4 2 3 1 7 6 Consider the following algorithm that builds the set of regions by starting from a single region encompassing the whole plane, and iteratively refines the set of regions by processing one line at a time. Activate 1: function BUILD ARRANGEMENT (lines) [new region spanning whole plane] lines do for region regions do if line intersects region then Append region to old 2: 3: regions for line 4: old[] 5: new [] 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: return regions left, right split region through line Append left to new Append right to new for xold do Remove x from regions for x = new do Append x to regions a) Prove that at the beginning of the ith iteration of the for loop in Line 3 the line cuts through exactly i regions from the previous iteration. b) Prove that at the end of the ith iteration of the for loop in Line 3 2+1+2 regions. Remember to use the fact that no three lines intersect in the same point! we have