Bentley Ottmann扫描线算法中，事件队列（event queue）的空间规模？

刚刚找到了On vertical visibility in arrangements of segments and the queue size in the Bentley-Ottmann line sweeping algorithm这篇文章。这篇文章证明了空间规模是不超过[img]https://www.zhihu.com/equation?tex=O%28n%5Clog%5E2%7Bn%7D%29[/img] 的，但没有说明是一个tight bound。 =============== Bentley Ottmann算法作为最常用的扫描线求交算法之一，是很多大学里面都会教的一个算法。它的时间复杂度很好辨析，是[img]https://www.zhihu.com/equation?tex=O%28%28n%2Bk%29%5Clog%7Bn%7D%29[/img] ，其中[img]https://www.zhihu.com/equation?tex=n[/img] 是线段数，[img]https://www.zhihu.com/equation?tex=k[/img] 是交点数。但是对于它的空间复杂度的分析，却总是很含糊。 其中主要是event queue所占据的空间不好分析。event queue最多可能将所有线段的顶点事件以及交点事件加入进来，所以通常认为它的空间复杂度为[img]https://www.zhihu.com/equation?tex=O%28n%2Bk%29[/img] 。但是如果[img]https://www.zhihu.com/equation?tex=k%3DO%28n%5E2%29[/img] 的话，也就是说交点个数是[img]https://www.zhihu.com/equation?tex=n%5E2[/img] 规模下的，那么这里event queue的最坏情况下的空间规模是不是[img]https://www.zhihu.com/equation?tex=O%28n%5E2%29[/img] 呢？ 如果是的话，能不能举出这个worst case呢？ Brown通过对原算法中关于进入event queue的实现进行修改，从而优化了event queue的空间规模为[img]https://www.zhihu.com/equation?tex=O%28n%29[/img] 。但是我想问的是原算法实现中空间规模的讨论，如果原实现中event queue的最坏情况下也到不了[img]https://www.zhihu.com/equation?tex=O%28n%5E2%29[/img] 的话，那么也许就可以证明Brown的优化是没有意义的了。