Hey gagra, great suggestion! The reason we use a BST instead of a heap is a bit hidden: In line 4 of findNewEvent (see the next video, Part III: Algorithmic Details), we have to check whether the intersection point of two neighboring segments already exists in the event queue. This is an operation that we cannot do in O(log n) time on a heap. We could store all points that we already found and then do this test in O(log n) time, but that defeats the advantages of a heap. Also, in the improvement of the space consumption (very last slide, Part V: Running Time) from O(n+k) to O(n), we have to remove points from the queue, which we also cannot do fast enough on a heap.

@@PhilippKindermann I checked out the second video and now i see why you use a BST for a general case, thanks for an explanation. However in my case I am not looking for all intersection, I am looking for the first one (I just need to verify that a set of segements in not self intersecting) so in my case 1) the segments never change order on the sweep line, case when they do they have an intersection and I simply quit the routine 2) I never have to add anything else except for initial points to the event queue for the same reason. This kinda simplifies the task alot from the algorithimc perspecitive and many things that you handle in the general case I can just omit. So in my special case it still looks like the binary heap would work. Another bonus of a binary heap in my scenario is that to construct a heap out on N points you need O(N) operations, while an incremental construction of a BST would require O(N log(N)). And of course despite the fact that a self balancing BST and a heap have the same assimptotic complexity O(log(N)) of the exctact min operation the binary heap has a way smaller constant assosiated with it since you just need to sink a single element after you grab your min element and this is much more simple than a remove operation of a BST that may require a sequence of rotations. I see you have a whole bunch of videos on computational geometry. That is cool, keep it going man! I will check them out.

@@gagra1234 This is true, if you only want to find any intersection, then you don't need a binary tree. In this case, you could even store all the points in a sorted list / array, since your event queue is static (we only add intersection points to the event queue, but you stop as soon as you find one). Then construction takes O(n log n) time, but you only need constant time for extraction; this should give you even smaller constants. Thank you for your kind words!

or does the algorithm only sees the intersections as event points only because it has seen it previously from checking the two segments?

@@102petar Your second thought is correct. To find that intersection point, you first have to process the two segments that intersect in that point. So you still require the O(n log n + I) running time.

I used ipe, a vector drawing program with ipe support by the one and only Otfried Cheong: ipe.otfried.org/

@@PhilippKindermann Thanks! I used pipe since about a year, but i didn't have idea that I can make presentations with it!

The reason I didn't use a MaxHeap is that deletion cannot be done trivially in logarithmic time. Otherwise a MaxHeap would be easier, that's true.