Dynamic planar convex hull operations in near-logarithmic amortized time

Research output: Contribution to journalArticlepeer-review


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+ε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.

Original languageEnglish (US)
Pages (from-to)1-12
Number of pages12
JournalJournal of the ACM
Issue number1
StatePublished - Jan 2001
Externally publishedYes


  • Computational geometry
  • Convex hulls
  • Dynamic data structures

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


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

Cite this