1. The contour of a collection of shapes is the boundary of the intersection of these shapes against the space. For examples, the red line surrounding the rectangles below is the contour of the shapes. In this problem you will explore algorithms that compute the contour of access-aligned rectangles (upright) that are with bottom edges collinear (all bottom edges of the rectangles are incident on the x-axis) as shown below on the right.

Problem statement: Given a collection of rectangles R of size n, where a rectangle is given by a pair of vertices: the upper left corner and the lower right corner and for each rectangle the lower corner vertices lie on the x-axis, compute the contour C of the set.

Input: Set rectangles expressed as a pair of points: one for the upper left corner and one for the lower right corner. Output: Set of vertices that describe the contour of the set of rectangles

a)Describe an incremental algorithm to compute the contour of the set of rectangles. Whats the running time of the algorithm? What's the running time of your algorithm?

b)Describe a divide and conquer algorithm to compute the contour of the set of rectangles. Whats the running time of the algorithm? Write a recurrence for your solution and then solve the recurrence using tree method or master theorem if applicable.