2-dimensional Convex Hull, Dynamic (Convex Hull)

From Algorithm Wiki
Revision as of 10:19, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-dimensional Convex Hull, Dynamic (Convex Hull)}} == 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 == <pre>n: number of line segments h: number of point...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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