Зарегистрироваться
Восстановить пароль
FAQ по входу

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

  • Файл формата pdf
  • размером 116,76 КБ
  • Добавлен пользователем
  • Отредактирован
Chan T.M. Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time
University of Waterloo, Waterloo, Ontario, Canada
12 pages
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+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
  • Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.
  • Регистрация