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 tangent-finding. Updates take O(log(1+epsilon)n) amortized time and queries take O(log n) time each, where n is the maximum size of P and E 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 and O(log n) time per query.