1. You are given two x-monotone polygonal chains P and Q with a total of n...

  

Transcribed Image Text:

1. You are given two x-monotone polygonal chains P and Q with a total of n vertices between them. Prove that P and Q can intersect at most O(n) times. For full credit, you must give an exact bound on the number of intersections along with a formal proof for your bound. Pa Q 2. Does the bound in (1) still apply if the two polygonal chains are monotone with respect to different directions (e.g., one monotone with respect to z and the other monotone with respect to y)? Justify your answer. 1. You are given two x-monotone polygonal chains P and Q with a total of n vertices between them. Prove that P and Q can intersect at most O(n) times. For full credit, you must give an exact bound on the number of intersections along with a formal proof for your bound. Pa Q 2. Does the bound in (1) still apply if the two polygonal chains are monotone with respect to different directions (e.g., one monotone with respect to z and the other monotone with respect to y)? Justify your answer.