2-dimensional Convex Hull, Dynamic (Convex Hull)
Jump to navigation
Jump to search
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 |