Sweep-Line Algorithm complixity

238 Views Asked by At

Sweep Line Alg:- is a kind of algorithm that uses a conceptual sweep line or sweep surface to solve various problems/issues in Euclidean space geometric. It is one of the key techniques in computational geometry. in order to detect whether there are intersections among N segments in the plane in time complexity of $O(N$ $ log$ $ N)$

Why the complixity of Sweep-Line Algorithm is $O(n(log $ $n))$ ?

1

There are 1 best solutions below

0
On

It's somewhat unclear what you're asking (I'll explain why later).

A sweep line algorithm essentially sorts the sites of interest in a particular direction (e.g. from left to right). This is $O(n\log n)$. After that, most algorithms take linear time to process the data. $O(n)$. Therefore, the entire time for a sweep line algorithm is $O(n\log n+n)=O(n\log n)$.

In the question that you're asking and example you gave, it depends on which algorithm you're using and what the output should be. Since $N$ segments may intersect in $O(N^2)$ places, if you want to output all the intersections, that would have to take $O(N^2)$ time. So, it would be helpful to indicate the particular algorithm that interests you.