Chan T.M. Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time

University of Waterloo, Waterloo, Ontario, Canada
12 pagesWe 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+e 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(log3/2 n). The only previous fully dynamic solution was
by Overmars and van Leeuwen from 1981 and required O(log2 n) time per update and O(log n) time
per query.The Data Structure
More Queries
Remarks