$29
Assignment No: 3 Divide-and-Conquer Algorithms Solution
You are given n non-vertical lines L0, L1, L2, . . . , Ln−1. Each line Li is specified by two floating-point (DOUBLE) numbers mi and ci . The equation of Li is y = mi x + ci (a vertical line cannot be so represented). You are sitting at the point (0, ∞), that is, infinitely above all finite points in the plane. The lines are assumed to be opaque. As you look down, you can see a portion of the plane delimited by portions of the lines. Your task is to find out your region of visibility as defined by the lines. The following figure illustrates this concept. In this assignment, assume that the lines are in general position, that is, no two of the given lines are parallel, and no three of the given lines are concurrent.
6
4 Region of Visibility
1
5
0
3
2 8 7
Part 1: Data types
Define a data type to store a line (two DOUBLE values m and c). You may additionally require to store the line number (an integer in the range [0, n − 1]) in each line structure. You have to work with points of intersection of lines, so define an additional data type to store a point in the two-dimensional plane (again two DOUBLE values x and y).
Part 2: The First Algorithm
A little bit of geometric insight suggests that the steepest line with negative slope and the steepest line with positive slope must constitute the first and the last portions of the region of visibility. In between them, you have finite segments of some other lines. Implement the following algorithm (given in pseudocode) in a function METHOD1 for the determination of the region of visibility.
1. Find the line with the smallest slope. Mark this as the current line K. Also initialize the current point to Q = (−∞, ·).
2. So long as it is possible to add another line, repeat the following steps.
(a) Let K = Li be the current line.
(b) Find the points of intersection Pi j of Li with all other lines L j which are not already included in the boundary of the region of visibility (maintain an array of visibility flags).
(c) Do not consider any Pi j if x(Pi j ) < x(Q) (where Q is the current point). If no such j exists, you are done, so break the loop.
(d) Find the intersection point Pi j∗ for which x(Pi j∗ ) is smallest among all Pi j with x(Pi j ) > x(Q).
(e) Add, to the boundary of the region of visibility, the segment of L j∗ from the current point Q to the intersection point Pi j∗ .
(f) Update the current line K to L j∗ , and the current point Q to Pi j∗ .
Evidently, this algorithm has a worst-case running time of O(n2), because it expends O(n) effort for discovering each segment on the boundary of the region of visibility.
— Page 1 of 4 —
Part 3: Precomputation for the Second Algorithm
We want to come up with an O(n log n)-time algorithm for the visibility problem. This algorithm requires the input lines be sorted in the increasing order of their slopes. Implement merge sort for this purpose. Assume that no two lines are parallel, so there is no duplicate slope among the input lines. You should write your own merge-sort function. We need a worst-case O(n log n)-time sorting algorithm for the given problem, so do not implement any worst-case Θ(n2)-time sorting algorithm.
Part 4: The Second Algorithm
An O(n log n)-time algorithm is now sketched. In view of Part 3, we assume that the n lines are sorted in the increasing order of their slopes. This has already taken O(n log n) time. The rest of the algorithm finishes in O(n) time only.
Consider the lines in the sorted order. The line with the smallest slope must be the first part of the boundary of the region of visibility. Suppose that Li1 , Li2 , . . . , Lik are the lines appearing in that sequence in the current boundary. You now consider the next line L j from the sorted list. Depending upon the position of the next line L j , the boundary changes to Li1 , Li2 , . . . , Lit , L j for some t in the range 1 6 t 6 k. The following figure demonstrates this incremental construction.
Change of the boundary of the region of visibility
for three different positions of the next line
(a) (b) (c)
Figure out how you determine t (that is, the segments that you need to throw for incorporating the next line).
Use a stack to store the growing and shrinking boundary (you may use an STL stack). Write a function
METHOD2 to implement this algorithm. The function should run in O(n) time in the worst case.
The MAIN() function
• Read n followed by n pairs (mi , ci ) for i = 0, 1, 2, . . . , n − 1. Store the lines in an array. Print the lines in the format given in the sample output.
• Call METHOD1 to compute and print the boundary of visibility.
• Sort the lines by your merge-sort function. Print the lines in the sorted order.
• Call METHOD2 to compute and print the boundary of visibility.
— Page 2 of 4 —
Sample output
The output given below corresponds to the lines in the figure of the first page. This figure is repeated below with coordinate lines shown. The bottom left corner is the origin (0, 0). Larger sample(s) can be found at the lab website.
6
4
Region of
Visibility
1
5
0
3
2
8
7
n = 9
0.4000000000 3.0000000000
-0.2000000000 9.0000000000
1.1200000000 -2.8000000000
0.0000000000 1.5000000000
-1.0000000000 12.0000000000
-0.4000000000 7.0000000000
-2.3076923077 15.0000000000
3.7500000000 -35.6250000000
0.7000000000 -3.5000000000
+++ Lines before sorting
Line
0: y =
0.4000000000
x +
3.0000000000
Line
1: y =
-0.2000000000 x +
9.0000000000
Line
2: y =
1.1200000000
x -
2.8000000000
Line
3: y =
0.0000000000
x +
1.5000000000
Line
4: y =
-1.0000000000 x +
12.0000000000
Line
5: y =
-0.4000000000 x +
7.0000000000
Line
6: y =
-2.3076923077 x +
15.0000000000
Line
7: y =
3.7500000000
x -
35.6250000000
Line
8: y =
0.7000000000
x -
3.5000000000
+++ Method
1
Line
6: From MINUS_INFINITY to (2.2941176471,9.7058823529)
Line
4: From (2.2941176471,9.7058823529) to (3.7500000000,8.2500000000)
Line
1: From (3.7500000000,8.2500000000) to (8.9393939394,7.2121212121)
Line
2: From (8.9393939394,7.2121212121) to (12.4809885932,11.1787072243)
Line
7: From (12.4809885932,11.1787072243) to PLUS_INFINITY
+++ Lines after sorting
Line
6: y =
-2.3076923077 x +
15.0000000000
Line
4: y =
-1.0000000000 x +
12.0000000000
Line
5: y =
-0.4000000000 x +
7.0000000000
Line
1: y =
-0.2000000000 x +
9.0000000000
Line
3: y =
0.0000000000
x +
1.5000000000
Line
0: y =
0.4000000000
x +
3.0000000000
Line
8: y =
0.7000000000
x -
3.5000000000
Line
2: y =
1.1200000000
x -
2.8000000000
Line
7: y =
3.7500000000
x -
35.6250000000
+++ Method 2
Line
6: From MINUS_INFINITY to (2.2941176471,9.7058823529)
Line
4: From (2.2941176471,9.7058823529) to (3.7500000000,8.2500000000)
Line
1: From (3.7500000000,8.2500000000) to (8.9393939394,7.2121212121)
Line
2: From (8.9393939394,7.2121212121) to (12.4809885932,11.1787072243)
Line
7: From (12.4809885932,11.1787072243) to PLUS_INFINITY
Submit a single C/C++ source file. Do not use global/static variables.
— Page 3 of 4 —
A theoretical exercise
Here is a divide-and-conquer algorithm that does not use merge sort. Use a linear-time algorithm to find the line with the median slope value. Partition the set of lines with respect to this median-slope line into two (almost) equal-sized halves. Recursively construct the regions of visibility of the two halves. Propose an O(n)-time algorithm to merge the two recursively constructed regions into one. The following figure illustrates that the merging procedure first needs to locate the intersecting segments in the two recursively computed boundaries.
Second boundary
First boundary Second boundary First boundary
(a) (b)
Two illustrations of merging
The running time of this algorithm satisfies T (n) = 2T (n/2) + O(n). By the master theorem, we have
T (n) = O(n log n).
— Page 4 of 4 —
