Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time

We give a data structure that allows arbitrary insertions and deletions on a planar point set P and supports basic queries on the convex hull of P , such as membership and tangentfinding. Updates take O(log 1+" n) amortized time and queries take O(log n) time each, where n is the maximum size of S and " is any fixed positive constant. For some advanced queries such as bridge-finding, both our bounds increase to O(log 3=2 n). The only previous fully dynamic solution was by Overmars and van Leeuwen from 1981 and required O(log 2 n) time per update. 1 Introduction Although the algorithmic study of convex hulls is as old as computational geometry itself, the basic problem of optimally maintaining the planar convex hull under insertions and deletions of points [28, 32] remains unsolved and has been regarded by some as one of the foremost open problems in the area [13, 25]. Besides its natural appeal, such a dynamic data structure has a wide range of applications, as it is often used..