Dynamic planar convex hull operations in near-logarithmic amortized time

Abstract

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+ε n ) amori tzed time and queries take O (log n time each, where n is the maximum size of P 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 ² n ) time per update and O (log n ) time per query.