2-dimensional Convex Hull, Dynamic: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
Line 12: Line 12:
== Parameters ==  
== Parameters ==  


n: number of line segments
$n$: number of line segments


h: number of points on the convex hull
$h$: number of points on the convex hull


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 24: Line 24:
|-
|-


| [[Incremental convex hull algorithm; Michael Kallay ( Convex Hull)|Incremental convex hull algorithm; Michael Kallay]] || 1984 || $O(n log n)$ ||  || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/002001908490084X Time]
| [[Incremental convex hull algorithm; Michael Kallay ( Convex Hull)|Incremental convex hull algorithm; Michael Kallay]] || 1984 || $O(n \log n)$ ||  || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/002001908490084X Time]
|-
|-
| [[Dynamic 2-d Convex Hull, Overmars and van Leeuwen (2-dimensional Convex Hull, Dynamic Convex Hull)|Dynamic 2-d Convex Hull, Overmars and van Leeuwen]] || 1980 || $O(log^{2}(n)$) per operation, $O(n*log^{2}(n)$) total ||  || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/002200008190012X?via%3Dihub Time]
| [[Dynamic 2-d Convex Hull, Overmars and van Leeuwen (2-dimensional Convex Hull, Dynamic Convex Hull)|Dynamic 2-d Convex Hull, Overmars and van Leeuwen]] || 1980 || $O(log^{2}(n)$) per operation, $O(n*log^{2}(n)$) total ||  || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/002200008190012X?via%3Dihub Time]

Latest revision as of 08:19, 10 April 2023

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