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 approach.

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$]$

$2.$ Using the function CombineSkeletons$($H$1,$ H$2)$ from Question $2\mathrm{.}1$ your task is to design a Divide$-$and$-$Conquer algorithm that computes the top skeleton of a set S of n horizontal line segments in the plane.

Each segment Si in S is represented $($as above$)$ as a triple $($li$,$ ri$,$ hi$).$ An example of the input instance is given in Fig. $1($left$)$ and the top skeleton is highlighted in Fig. $1($right$).$

The output must follow the input format to CombineSkeletons stated in Question $2\mathrm{.}1,$ that is$,$ list the horizontal segments in the top skeleton from left to right. For example, Question $2[48$ points$]$

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,).$ 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 $(,$ ri$,$ hi$)$ where li and ri denote

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

coordinate 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 prothe top skeleton shown Fig. $1($right$)$ must be listed as:

$023$

$244$

$452$

$563$

$674$

$783$

$9113$

$11121$

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

$($and assuming that CombineSkeletons runs in O$($n$)$ time$)$ the algorithm should run

in O$($n log time where n is the number of segments in S$.[9$ points$]$

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

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