2-dimensional Convex Hull, Dynamic (Convex Hull)

Description

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

Parameters

$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