2-dimensional Convex Hull, Online (Convex Hull)

From Algorithm Wiki
Jump to navigation Jump to search


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


$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