Dynamic Planar Convex Hull with Optimal Query Time and O(log nĚloglog n) Update Time

Gerth Stølting Brodal and Riko Jacob

Technical Report, ALCOMFT-TR-01-34, ALCOM-FT, 14 pages, May 2001.

Abstract

The dynamic maintenance of the convex hull of a set of points in the plane is one of the most important problems in computational geometry. We present a data structure supporting point insertions in amortized O(log nĚlogloglog n) time, point deletions in amortized O(log nĚloglog n) time, and various queries about the convex hull in optimal O(log n) worst-case time. The data structure requires O(n) space. Applications of the new dynamic convex hull data structure are improved deterministic algorithms for the k-level problem and the red-blue segment intersection problem where all red and all blue segments are connected.

Online version

alcomft-tr-01-34.pdf (178 Kb)

BIBTEX entry

@techreport{alcomft-tr-01-34,
  author = "Gerth St{\o}lting Brodal and Riko Jacob",
  institution = "ALCOM-FT",
  month = "May",
  number = "ALCOMFT-TR-01-34",
  pages = "14",
  title = "Dynamic Planar Convex Hull with Optimal Query Time and {$O(\log n\cdot\log\log n)$} Update Time",
  year = "2001"
}