[Hints: 1) Argue it suffices to check the width of the river only at a discrete set of x values. 2) Use a plane sweep algorithm. Argue that between polygon vertices, the width of the sweep lines cut can be expressed as a simple function of x. How can you quickly update this function during events?]

3. (35 points) A civil engineer has asked for your help in analyzing whether a dangerous portion of a river will flood. He presents you with the following (admittedly rather unrealistic) model of the river. The portion of the river of interest is modeled as an x-monotone polygon P that is bounded between two vertical line segments at x=xand x=x+, of widths wand w+, respectively (see Figure 3 ). Inside the polygon are some number of disjoint x-monotone polygons that represent islands in the river. Let n denote the total number of vertices, including both the outer banks of the river and the islands. Figure 3. The portion of the river that may flood. The engineer tells you that in order to avoid a flood, the width of the river (not counting islands) at every vertical cut must be at least some minimum value wmin. For example, in the figure, the sum of the lengths of the two blue vertical segments at x=x0 must be at least wmin in order to avoid a flood. Given the polygon P, the polygon islands, and the value wmin, present an O(nlogn) time algorithm that determines whether the river will flood, that is, whether there is a vertical cut whose total width is smaller than wmin