1
$\begingroup$

enter image description here

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(n\log 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(2\log 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(2\log n+R)$ in total.

We do this $n$ times (the amount of horizontal segments) so we get a complexity of $O(2n\log n+nR)$.

$\endgroup$
3
$\begingroup$

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 $O\log n + R_h$ time, where $R_h$ are the intersections you output. Then the overall running time is $$\sum_h \log n + R_h = n\log n +R.$$

Simply speaking, you only output every crossing once. So the overall time for the output is $O(R)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.