@Evil In this case, the "status" data structure represents the beach-line. We need a self-balancing BST or, in general, a data structures which has O(n) space complexity and O(log(n)) time complexity, to search, insert and delete elements from it, because we want to maintain our algorithm under an O(n*log(n)) time complexity. In the Furtune's algorithm, we may also need to detete certain events from the queue, so I think we also need a self-balancing BST to implement it.

@Evil But I also like these discussions here. I think we can learn a lot from each other if we discuss. Furthermore, I think this chat deserves more activity, given the importance of CS.