Content deleted Content added
Line 28:
The algorithm does not need to maintain explicitly a representation of the sweep line ''L'' or its position in the plane. Rather, the position of ''L'' is represented indirectly: it is the vertical line through the point associated with the most recently processed event.
The binary search tree may be any [[Self-balancing binary search tree|balanced binary search tree]] data structure, such as a [[red-black tree]]; all that is required is that insertions, deletions, and searches take logarithmic time. Similarly, the priority queue may be a [[binary heap]] or any other logarithmic-time priority queue; more sophisticated priority queues such as a [[Fibonacci heap]] are not necessary. Note that the space complexity of the priority queue depends on the data structure used to implement it.
==Detailed algorithm==
| |||