The next two questions $(2\mathrm{.}1$ and $2\mathrm{.}2)$ will look at the top skeleton problem. The top

skeleton of a set S of n line segments in the plane is an important concept for many

applications, including visibility and motion planning. The segments are regarded as

opaque obstacles, and their top skeleton consists of the portion of the segments visible

from the point $(0,\backslash$infty $).$ We will study the special case where all the segments in S are

horizontal segments with y$-$coordinates greater than or equal to $0.$

An example of the input is given in Fig. $1($left$)$; the corresponding output is given in

Fig. $1($right$).$

A horizontal segment si in S is represented by the triple $($li$,$ ri$,$ hi$)$ where li and ri denote

the left and right x$-$coordinates of the segment respectively, and hi denotes the ycoordinate

of si$.$ The input is a list of triples; one per segment. The output is the top

skeleton specified as a list of horizontal segments arranged in order by their left

x$-$coordinates. For the example shown in Fig. $1,$ the input and output are: $2\mathrm{.}1$ We will solve the top skeleton problem using a divide$-$and$-$conquer ap$-$proach.

Recall from the lecture that a divide$-$and$-$conquer algorithm works by recursively

breaking down a problem into smaller subproblems of the same type, until these become

simple enough to be solved directly. The solutions to the subproblems are then combined

into a solution to the original problem. Your task for Question $2\mathrm{.}1$ is to handle the

combine step. That is$,$ as a subroutine to the divide$-$and$-$conquer algorithm $($Question

$2\mathrm{.}2)$ you will need CombineSkeletons$($H$1,$ H$2)$ that takes two top skeletons as input and

produces a single top skeleton H of them. An example is shown in Fig. $2,$ where two top

skeletons are given as input and $$combined$$ into a single top skeleton.

You may assume that the two top skeletons passed as arguments to CombineSkeletons are

given as a list of horizontal segments ordered from left to right.

$($a$)$ Description of how your algorithm works $($in plain English$).$ For full points the

algorithm should run in O$($n$)$ time where n is the total number of segments in H$1$

and H$2.[10$ points$]$

$($b$)$ Argue why your algorithm is correct. $[8$ points$]$

$($c$)$ Prove an upper bound on the time complexity of your algorithm. $[6$ points$]$