# Dynamic Planar Convex Hull

## Gerth Stølting Brodal and Riko Jacob

In * Proc. 43rd Annual Symposium on Foundations of Computer Science*, pages 617-626, 2002.

## Abstract

In this paper we determine the computational complexity of the dynamic
convex hull problem in the planar case.
We present a data structure that maintains a finite set of n points in
the plane under insertion and deletion of points in amortized O(log n)
time per operation. The space usage of the data structure is O(n).
The data structure supports extreme point queries in a given
direction, tangent queries through a given point, and queries for the
neighboring points on the convex hull in O(log n) time. The extreme
point queries can be used to decide whether or not a given line
intersects the convex hull, and the tangent queries to determine
whether a given point is inside the convex hull.
We give a lower bound on the amortized asymptotic time complexity that
matches the performance of this data structure.

**Copyright notice**
Copyright © 2002 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

**Online version**

focs02.pdf (172 Kb)

**DOI**

10.1109/SFCS.2002.1181985

**BIBT**_{E}X entry

@inproceedings{focs02,
author = "Gerth St{\o}lting Brodal and Riko Jacob",
booktitle = "Proc. 43rd Annual Symposium on Foundations of Computer Science",
doi = "10.1109/SFCS.2002.1181985",
isbn = "0-7695-1822-2",
pages = "617-626",
title = "Dynamic Planar Convex Hull",
year = "2002"
}