Problem Detail: 
In the same lecture notes without providing many details it says that the complexity of the algorithm which uses a balanced search tree is $O(nlog n+R)$ where $R$ is the total amount of intersections. However I don’t understand why this is the case. Suppose that the sweep line is travelling from top to bottom. Whenever we encounter a vertical line segment, we pick its $x$ coordinate and add it to a search tree. Assuming that we are using a balanced search tree like AVL, this operation will take $O(log n)$ time. Now when we reach an end point of a vertical line segment, we remove its $x$ coordinate from the search tree, which is going to take $O(log n)$ time as well. Whenever we encounter a horizontal line segment defined by points $A$ and $B$, we have to do a range search on our search tree and use the range defined by these two points, that is $(A.x, B.x)$ Now how is this range search going to happen? We use $A.x$ and travel to the left most point in the search tree, and do the same for $B.x$, we can do this in $O(2log n)$. All the points in our tree between these two end points are going to be the intersecting the horizontal segment, which is going to be let’s say $R$ in total, so $O(2log n+R)$ in total. We do this $n$ times (the amount of horizontal segments) so we get a complexity of $O(2nlog n+nR)$.
In the same lecture notes without providing many details it says that the complexity of the algorithm which uses a balanced search tree is $O(nlog n+R)$ where $R$ is the total amount of intersections. However I don’t understand why this is the case. Suppose that the sweep line is travelling from top to bottom. Whenever we encounter a vertical line segment, we pick its $x$ coordinate and add it to a search tree. Assuming that we are using a balanced search tree like AVL, this operation will take $O(log n)$ time. Now when we reach an end point of a vertical line segment, we remove its $x$ coordinate from the search tree, which is going to take $O(log n)$ time as well. Whenever we encounter a horizontal line segment defined by points $A$ and $B$, we have to do a range search on our search tree and use the range defined by these two points, that is $(A.x, B.x)$ Now how is this range search going to happen? We use $A.x$ and travel to the left most point in the search tree, and do the same for $B.x$, we can do this in $O(2log n)$. All the points in our tree between these two end points are going to be the intersecting the horizontal segment, which is going to be let’s say $R$ in total, so $O(2log n+R)$ in total. We do this $n$ times (the amount of horizontal segments) so we get a complexity of $O(2nlog n+nR)$.
Asked By : jsguy
Answered By : A.Schulz
It’s a bit hard to get through your text since a lot of information is missing. However I assume that you have the following misunderstanding. Let me ignore the constants in the big-O for this argument since this is irrelevant. For every horizontal segment $h$ you perform an action that takes $Olog n + R_h$ time, where $R_h$ are the intersections you output. Then the overall running time is $$sum_h log n + R_h = nlog n +R.$$ Simply speaking, you only output every crossing once. So the overall time for the output is $O(R)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33681
