Please answer this question with all the steps shown properly.

Part B (Group, 70 marks) In graphics rendering, different objects are sometimes overlaid on top of one another, and only their "combined result" is displayed; anything hidden behind other objects (or the parts of them hidden) need not be drawn. This question considers a simplified scenario, where the objects are all rectangles lying on the same horizontal base. The combined image takes the form of a sequence of line segments that outlines the parts of the rectangles not blocked by others. We call this the envelope of all the rectangles. (You can think of the rectangles as buildings and the envelope as the view of these buildings from far away horizontally.) For example, in the top half of the figure below, there are six rectangles, and their envelope is the grey line segments in the bottom half of the figure. In this question everything is in a standard xy coordinate system, where the bottom of each rectangle lies on the x-axis. Each rectangle is specified by three numbers (x1,x2,h) indicating that it is situated between x-coordinates x1 and x2 and has height h. The envelope of a set of rectangles is a set of horizontal and vertical line segments. They can be represented by a sequence of coordinates (x1,h1),(x2,h2),,(xk,hk),(xk+1,0), which indicates that there is a horizontal line segment of height h1 from x-coordinate x1 onwards, until it reaches the x coordinate x2 where the height becomes h2, until it reaches x3 where the height becomes h3, and so on. It is implicitly assumed that the height is 0 for all x-coordinates before x1, and stays at 0 all the way after xk+1. The vertical line segments can be implied from these coordinates and are not explicitly stated. Going back to the example in the figure, the six rectangles are (1,5,2),(3,4,4),(7,10,2),(8,12,1),(9,13,3),(11,14,4), and their resulting envelope can be represented by the sequence of coordinates (1,2),(3,4),(4,2),(5,0),(7,2),(9,3),(11,4),(14,0). In all the following, any input and output of your algorithms (rectangles and envelopes) should be assumed to be of this form, namely a list of coordinate pairs/triplets. Figure 1: Six rectangles (above) and their envelope (below). (a) In each of the following four cases, produce the envelope of the two given rectangles. You should both draw a picture and also write down the sequence of coordinates representing the envelope. Some of these are done for you as examples. [10 marks] (b) Describe an O(n) time algorithm that computes the new envelope of adding one rectangle to an existing envelope, where n is the number of points (coordinate pairs) of the existing envelope. (For this part only) you can describe your algorithm informally and without justification of its correctness and time complexity. [15 marks] Using (b), a straightforward O(n2) algorithm to compute the envelope of n rectangles can be obtained easily. But we want to design a more efficient algorithm. (c) Design an algorithm that merges two envelopes, each consisting of at most n coordinate pairs, into one envelope. The algorithm should rum in O(n) time. You should give some intuition/explanation of your algorithm, express it in pseudocode, and justify its time complexity. [25 marks] (d) Design an O(nlogn) time algorithm to compute the envelope of n rectangles. You should give some intuition/explanation of your algorithm, express it in pseudocode, and prove its time complexity. You can assume n is a power of 2. (Hint: use divide and conquer and (c).) (The envelope resulting from the merging of n rectangles has at most O(n) coordinate pairs - you do not need to prove this fact.) [20 marks]