segment intersections question

Please find attached, please have the answer typed up

Q7 Practice problem 10 (segment intersections)
15 Points
a) At the end of the solution for practice problem 10, there is a statement about interval trees
being too slow.
The idea would have been to treat each segment as an infinitely thin rectangle, and apply the
solution to problem 9.
So, why is this too slow?
Enter your answer here
b) Define a “diagonal segment” to be any segment that has an angle of 45 degrees, shaped like
this: /
Suppose that the input consists of n diagonal segments and n horizontal segments, instead of
vertical and horizontal.
Does the same algorithm work without modification? Does it work only if we make some
changes? Or is there no hope solving this in O(n log n) time?
Explain.
Enter your answer here
10. Consider a set S of 2n line segments in 2D: n horizontal and n vertical. Assume that no
segment has endpoints at the same x-coordinate or y-coordinates as any other segment.
Provide a sub-quadratic-time algorithm (i.e., O(na) doesn’t suffice) to count how many
intersections there are among the segments in S. Note that you do not need to list the
intersections. Just report how many there are. In the example below the output is: 5.
TEL
Answer:
Given the assumption stated, no horizontal segments overlap each other, and no ver-
tical segments overlap each other. So we are only looking for intersections of vertical
vs horizontal segments. Sort all endpoints by y-coordinate, along with their “type”
(belonging to a horizontal or vertical edge, and in the latter case, whether they are the
top or bottom end of the edge). Then scan through this sorted list. Every time we
find a bottom endpoint of a vertical segment, we insert the segment into a balanced
BST, using its x-coordinate as a key. Every time we find the top endpoint of a vertical
segment, we delete its entry from the BST. This can be visualized as scanning through
the 2D data from bottom to top with a horizontal line. At any point in time, the BST
will represent exactly the set of vertical segments intersected by this horizontal sweep-
ing line. In fac at every point in time the BST will contain the x-coordinates of all the
vertical segments that the sweep-line currently intersects, naturally in sorted order. So
far, we have ignored elements in the sorted list that correspond to horizontal segments.
As we scan through the sorted list, every time we find such an element, we will perform
a range counting query in the BST, using the corresponding horizontal segment as the
query range. So, whenever our sweep line overlaps a horizontal segment, h, we find
out the number of overlaps that it is involved in, by spending logarithmic time.
This algorithm takes O(n log n) time to sort all the endpoints. Then we set up an
empty BST and we have a mix of n insertions, n deletions, and n range counting
queries. We have seen how to maintain a balanced augmented BST that supports
these operations and allows range counting, all in O(log n) time per operation, so the
total time is O(n log n).
Note: Sweeping with an interval tree is too slow.