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.Introduction The Data Structure More Queries Remarks
Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.