In the Bentley–Ottmann algorithm, Regarding :

Find the segments r and t that are immediately below and above s in T (if they exist) and if their crossing forms a potential future event in the event queue, remove it.

That means, every insertion of a segmant may lead to an intersection event deletion.

I am thinking what makes it stay within the said time complexity.

Is it valid to say that it is because i have up to n such insertions that would lead to up to n such deletions, which causes O(nlogn) operations at most hence the time complexity is not effected?

  • 1
    $\begingroup$ Do you have any particular reason to doubt your explanation? Otherwise, there is no need ask for validation from this online community. Trust yourself more. $\endgroup$ Feb 12, 2016 at 15:18
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. What is the root cause of your uncertainty? Is there some concept you don't fully understand? What prevents you from answering your own question? $\endgroup$
    – D.W.
    Feb 12, 2016 at 18:22


Your Answer

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

Browse other questions tagged or ask your own question.