CS29003 -  ALGORITHMS LABORATORY - Assignment 2 - Divide - Conquer - Solved

Problem Statement
You have joined as a trainee in an Institution researching on creating devices to help people with defective eyesight. You have been assigned to a group which deals with the binary eyesight defect, where a person can only see 2 colors, black and white. This means that when 2 objects have a greater contrast than a particular threshold, then they can be perceived as different.

They are at the initial phases of the project and they want to understand and stress on the difficulties faced by these people in recognizing objects and the loss of depth perception.

Since you are still a trainee you have been tasked to get the perspective of users on a set of rectangular objects kept on a table.

Imagine that you are looking right at it, and you cannot see the top of these objects (this simulates the irrelevance of depth information). The objects are of various colours and the background is white, and it is known that the defective eye will not be able to differentiate between each of the objects but there is enough contrast to differentiate between the objects and the background.

Using the divide and conquer technique, devise an algorithm to convert the input of a normal vision (Figure 1(a)) to that of the defective vision (Figure 1(b)), and implement it in C++/C .

 

                                    (a) objects appearing to normal vision                (b) objects appearing to defective vision

Figure 1: Images as seen by the 2 visions
Note: Figure 1(b) does not accurately represent the image perceived by the defective eye. The silhouette would be completely filled in that case.

Input
The number of rectangular boxes N. The geometric information of each rectangular box is represented by a triplet of integers [Li,Ri,Hi], where Li and Ri are the x coordinates of the left and right edge of the ith box, respectively, and Hi is its height. It is guaranteed that:

0 6 Li,Ri 6 INT MAX

0 < Hi 6 INT MAX

Ri − Li > 0

You may assume all boxes are perfect rectangles grounded on an absolutely flat surface at height 0.

Output
The output is a list of “key points” (red dots in Figure 1(b)) in the format of

[[x1,y1],[x2,y2],[x3,y3],...]
A key point is the left endpoint of a horizontal line segment.

Note that the last key point, where the rightmost box ends, is merely used to mark the termination of the outline, and always has zero height. Also, the ground in between any two adjacent boxes should be considered part of the outline contour.

Na¨ıve Algorithm
This will be an incremental approach, where we will build the outline by merging it with every box in the order which is given. (Remember that the input is not sorted in any order) Here, the inputs are stored in boxes array described in detail in the Input section above.

 

typedef struct {

int left; // x coordinate of left side int ht; // height

int right; // x coordinate of right side

} Box;

typedef struct { // A Point in Outline int x; // x coordinate int y; // height or the y coordinate

} Point;

boxes is the input array of Box datatype

outline = [] // list of Point datatype, so that deletion and insertion costs O(1) for b_i in boxes: // O(N) find j in outline with b_i.left < outline_j.x // O(N) //need to combine this point with the outline

if outline_{j-1}.y>=b_i.ht: // if the height of the previous point is higher than this no need to make any changes else if outline_{j-1}.x==b_i.left: // if the prev point has the same position outline_{j-1}.y = b_i.ht // we know that this point has higher height

else insert a new point j++

for points in outline from index j to k where b_i.right<outline_k.x // O(N) do remove points from the outline where the height falls below that of b_i

//in the way we added the left point make a similar combination on the right point

(b_i.right, 0) end

 

Time complexity: O(N2)

Can you use Divide and Conquer to devise an algorithm with a complexity of O(Nlog(N))?

Sample Test Cases
Test Case 1
 

5

2      9 10

3      7 15

5 12 12

15 20 10

19 24 8

Outline :

[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

 

Test Case 2
 

7

0 5 7

5 10 7

5 10 12

10 15 7

15 20 7

15 20 12

20 25 7

Outline :

[[0,7],[5,12],[10,7],[15,12],[20,7],[25,0]]

 

Test Case 3
 

2

0 2 3

2 5 3

Outline : [[0,3],[5,0]]

 

Test Case 4
 

3

1 2 1

1 2 2

1 2 3

Outline :

[[1,3],[2,0]]

 

Implementation Instructions
We will be providing a header file, which you need to include in your program (C/C++).

All the input and output technicalities have been handled in the process() function of the header file. You are free to define structures and classes of your own but make sure to keep the end points compatible.