Description
A line segment s on the plane can be represented by four numbers, its slope s.m, the x coordinate
s.` of its left end point, the x coordinate s.r of its right end point, and the y intercept s.b of the
line containing s, provided s is not vertical. A vertical line segment s has slope s.m = ∞. It is
represented by the y coordinate s.` of its lower end point, the y coordinate s.r of its upper end
point, and the x intercept s.b of the line containing s.
A set of line segments S is disjoint if no two line segments in S intersect one another.
In this assignment, you will design algorithms that, given two sets of disjoint line segments,
S and S
0
, counts the number of (unordered) pairs of lines in S ∪ S
0
that intersect. For example,
if S is the set of two black lines and S
0
is the set of three red lines in Figure 1, then there are 3
intersecting pairs of lines.
Figure 1: The intersections between two sets of disjoint line segments
1. Suppose that s.` = 0 and s.r = 1 for each line segment s ∈ S ∪ S
0
, the line segments in S =
{s1, . . . , sn} are sorted in increasing order by their y intercepts (i.e. s1.b < s2.b < · · · < sn.b),
and the line segments in S
0 = {s
0
1
, . . . , s0
n0} are sorted in increasing order by their y intercepts
(i.e. s
0
1
.b < s0
2
.b < · · · < s0
n0.b). Give an algorithm (in pseudocode) that counts the number
of pairs of lines in S ∪ S
0
that intersect. Your algorithm must run in O(n + n
0
) time, where
n = |S| and n
0 = |S
0
|.
First, briefly explain, at a high level, how your algorithm works. Then give the pseudocode.
Your explanation should NOT be a line by line description of the pseudocode.
Explain why your algorithm runs in the required time.
2. Prove that your algorithm in part 1 is correct. If your code is iterative, carefully state
relevant loop invariants and prove that they are invariants by induction. If your code is
recursive, carefully state relevant properties of your algorithm and prove them by induction.
3. Suppose that, as in part 1, s
0
.` = 0 and s
0
.r = 1 for each line segment s
0 ∈ S
0
, and the
line segments in S
0 = {s
0
1
, . . . , s0
n0} are sorted in increasing order by their y intercepts (i.e.
s
0
1
.b < s0
2
.b < · · · < s0
n0.b). However, 0 ≤ s.` ≤ s.r ≤ 1 for each non-vertical line segment s ∈ S
and 0 ≤ s.b ≤ 1 for each vertical line segment s ∈ S. Give an algorithm (in pseudocode)
for determining the number of intersections between S and S
0
. Your algorithm must run in
O(n log n
0
) time, where n = |S| and n
0 = |S
0
|.
1
First, briefly explain, at a high level, how your algorithm works. Then give the pseudocode.
Your explanation should NOT be a line by line description of the pseudocode.
Explain why your algorithm runs in the required time.
4. Prove that your algorithm in part 3 is correct. If your code is iterative, carefully state
relevant loop invariants and prove that they are invariants by induction. If your code is
recursive, carefully state relevant properties of your algorithm and prove them by induction.
2
