In class we argued that the number of parabolic arcs along the beach line in Fortune's algorithm is at most 2n ? 1. The goal of this problem is to prove this result in a somewhat more general setting. Consider the beach line at some stage of the computation, and let {p1, . . . , pn} denote the sites that have been processed up to this point in time. Label each arc of the beach line with its associated site. Reading the labels from left to right defines a string. (In Figure 3 below, the string would be p3p2p1p2p4p6p7p8p6p3)

(a) Prove that for any i, j, the following alternating subsequence cannot appear anywhere within such a string: . . . pi . . . pj . . . pi . . . pj . . .

(b) Prove that any string of n distinct symbols that does not contain any repeated symbols (. . . pipi . . .) and does not contain the alternating sequence of the type given in part (a) cannot be of length greater than 2n ? 1. (Hint: Use induction on n.)

Problem 4. In class we argued that the number of parabolic arcs along the beach line in Fortune's algorithm is at most 21?. 1. The goal of this problem is to prove this result in a somewhat more general setting. Consider the beach line at some stage of the computation, and let {p1,. . . , pn} denote the sites that have been processed up to this point in time. Label each arc of the beach line with its the associated site. Reading the labels from left to right denes a string. (In Figure 3 below, the string would be pampwzmpspvpapsps) .J.. .- 4 H Jun-- H P3 P2 P1 P2 P4 P6 P7 P8 P6 P3 Figure 3: An example of beach line with label sequence p3p2p1p2p4p5p7pgpp3. (a) Prove that for any i, j, the following alternating subsequence cannot appear anywhere within such a string: \"pi"'pju'p'iu'pju' (b) Prove that any string of 'n. distinct symbols that does not contain any repeated symbols (. . .pp, . . .) and does not contain the alternating sequence of the type given in part (a) cannot be of length greater than 21?. 1. (Hint: Use induction on n.) Caution: The textbook already proved why there are at most 21?. 1 parabolic arm on the beach line. But, in this problem, we will prove the same result in a different way with general setting. So, you need to solve this problem with the property from (a) and DO NOT use the result from the textbook