2-dimensional Convex Hull (Convex Hull)

From Algorithm Wiki
Jump to navigation Jump to search


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


$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