2-dimensional Convex Hull, Dynamic (Convex Hull)

From Algorithm Wiki
Jump to navigation Jump to search


Here, the input points may be sequentially inserted or deleted, and the convex hull must be updated after each insert/delete operation.

Related Problems

Generalizations: 2-dimensional Convex Hull

Related: 3-dimensional Convex Hull, d-dimensional Convex Hull, 2-dimensional Convex Hull, Online


$n$: number of line segments

$h$: number of points on the convex hull

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Incremental convex hull algorithm; Michael Kallay 1984 $O(n \log n)$ Exact Deterministic Time
Dynamic 2-d Convex Hull, Overmars and van Leeuwen 1980 $O(log^{2}(n)$) per operation, $O(n*log^{2}(n)$) total Exact Deterministic Time
(many more...) Exact Deterministic