Dynamic planar convex hull operations in near-logarithmic amortized time

Research output: Contribution to journalConference articlepeer-review

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(log1+qq n) amortized time and queries take O(log n) time each, where n is the maximum size of P and qq 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.

Original languageEnglish (US)
Pages (from-to)92-99
Number of pages8
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Jan 1 1999
Externally publishedYes
EventProceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA
Duration: Oct 17 1999Oct 19 1999

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Dynamic planar convex hull operations in near-logarithmic amortized time'. Together they form a unique fingerprint.

Cite this