ALCOMFT-TR-01-34

Gerth Stølting Brodal and Riko Jacob
Dynamic Planar Convex Hull with Optimal Query Time and O(log nloglog n) Update Time
Århus. Work package 4. April 2001.

Abstract: 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 nlogloglog n) time, point deletions in amortized O(log nloglog 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.

Postscript file: ALCOMFT-TR-01-34.ps.gz (179 kb).