Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

The next two questions ( 2 . 1 and 2 . 2 ) will look at the top skeleton problem. The top skeleton of a

The next two questions (2.1 and 2.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,\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.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.1 is to handle the combine step. That is, as a subroutine to the divide-and-conquer algorithm (Question 2.2) you will need CombineSkeletons(H1, H2) 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 H1
and H2.[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(H1, H2) from Question 2.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.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.1 and 2.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.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]
image text in transcribed

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Professional Microsoft SQL Server 2012 Administration

Authors: Adam Jorgensen, Steven Wort

1st Edition

1118106881, 9781118106884

More Books

Students also viewed these Databases questions

Question

Write down the three Pythagorean Identities.

Answered: 1 week ago