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)$.

A.Schulz
12.3k1 gold badge43 silver badges64 bronze badges
asked Dec 1, 2014 at 9:48
$\endgroup$

1 Answer 1

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)$.

answered Dec 1, 2014 at 10:09
$\endgroup$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.