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

Gerth Stølting Brodal and Riko Jacob

In Proc. 7th Scandinavian Workshop on Algorithm Theory, volume 1851 of Lecture Notes in Computer Science, pages 57-70. Springer Verlag, Berlin, 2000.

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.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2000. All rights reserved.

Online version

swat00dch.pdf (247 Kb)

DOI

10.1007/3-540-44985-X_7

Links

BIBTEX entry

@incollection{swat00dch,
  author = "Gerth St{\o}lting Brodal and Riko Jacob",
  booktitle = "Proc. 7th Scandinavian Workshop on Algorithm Theory",
  doi = "10.1007/3-540-44985-X_7",
  isbn = "978-3-540-67690-4",
  pages = "57-70",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Dynamic Planar Convex Hull with Optimal Query Time and {$O(\log n\cdot\log\log n)$} Update Time",
  volume = "1851",
  year = "2000"
}

Other versions