Dynamic Planar Convex Hull with Optimal Query Time
Dynamic Planar Convex Hull with Optimal Query Time
复制标题
具有最佳查询时间的动态平面凸包
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
R. Jacob
中科院分区：
文献类型：
--
作者：
G. Brodal;R. Jacob
平面中一组点的凸壳的动态维护是计算几何学中最重要的问题之一。在Amortized O（log n log log n）时间中，以及有关最佳O（log n）最差时间的各种查询。结构是改进了K级问题的确定性算法以及所有红色和所有蓝色段都连接的RedBlue段交叉问题。
The dynamic maintenance of the convex hull of a set of points in the plane is one of the most important problems in computational geometry. We present a data structure supporting point insertions in amortized O(log n ċ log log log n) time, point deletions in amortized O(log n ċ log log n) time, and various queries about the convex hull in optimal O(log n) worst-case time. The data structure requires O(n) space. Applications of the new dynamic convex hull data structure are improved deterministic algorithms for the k-level problem and the redblue segment intersection problem where all red and all blue segments are connected.