Dynamic planar convex hull with optimal query time and \(O(\log n\cdot \log\log n)\) update time. (English) Zbl 0966.68522

Halldórsson, Magnús M. (ed.), Algorithm theory - SWAT 2000. 7th Scandinavian workshop, Bergen, Norway, July 5-7, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1851, 57-70 (2000).
Summary: 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\cdot\log \log \log n)\) time, point deletions in amortized \(O(\log n\cdot \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 red-blue segment intersection problem where all red and all blue segments are connected.
For the entire collection see [Zbl 0941.00039].


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)