# 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.

Online version

swat00dch.pdf (247 Kb)

DOI

10.1007/3-540-44985-X_7

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