2-dimensional Convex Hull (Convex Hull)

Description

The convex hull or convex envelope or convex closure of a set X of points in the Euclidean plane or in a Euclidean space (or; more generally; in an affine space over the reals) is the smallest convex set that contains X. Here, we are looking at the 2-dimensional case.

Related Problems

Generalizations: d-dimensional Convex Hull

Subproblem: 2-dimensional Convex Hull, Online, 2-dimensional Convex Hull, Dynamic

Related: 3-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
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

References/Citation

https://ecommons.cornell.edu/handle/1813/6417

https://ecommons.cornell.edu/handle/1813/6417