2-dimensional Convex Hull, Online (Convex Hull)

Description

Here, we are given the input points one by one, and must maintain the current convex hull after each input point.

Related Problems

Generalizations: 2-dimensional Convex Hull

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

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
Online 2-d Convex Hull, Preparata	1979	$O(logn)$ per operation, $O(n*log(n)$) total	$O(n)$	Exact	Deterministic	Time

References/Citation

https://dl.acm.org/doi/abs/10.1145/359131.359132

https://link.springer.com/content/pdf/10.1007/978-1-4612-1098-6.pdf