BIM Q&A | What is the Spatial Size of the Event Queue in Bentley-Ottmann’s Scanline Algorithm?
I recently came across an article titled “On vertical visibility in arrangements of segments and the queue size in the Bentley-Ottmann line sweeping algorithm”. This article proves that the spatial complexity of the event queue should not exceed , though it does not clarify whether this is a tight bound.
===============
The Bentley-Ottmann algorithm, widely taught in many universities, is one of the most common scanline algorithms for detecting line segment intersections. Its time complexity is well known as , where
is the number of segments, and
is the number of intersection points.
However, the spatial complexity of the algorithm is often ambiguous, particularly regarding the event queue’s size. The event queue can potentially hold all segment endpoints and intersection events. Therefore, its space complexity is usually considered to be .
But if , meaning the number of intersections is on the order of
, does the event queue’s worst-case space complexity then become
? If so, could you provide an example of such a worst-case scenario?
Brown improved the original algorithm by modifying how events are added to the event queue, optimizing its space complexity down to . However, my question concerns the space complexity in the original implementation. If the event queue in the original algorithm cannot reach a worst-case size of
, then perhaps Brown’s optimization might be unnecessary.
Must log in before commenting!
Sign Up