Bentley–Ottmann algorithm: Difference between revisions

Revision as of 05:45, 15 November 2021

Revision as of 18:04, 2 April 2022

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-blackred–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==