2-dimensional Convex Hull: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
Line 14: Line 14:
== 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 26: Line 26:
|-
|-


| [[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]
|-
|-
| [[Online 2-d Convex Hull, Preparata (2-dimensional Convex Hull, Online Convex Hull)|Online 2-d Convex Hull, Preparata]] || 1979 || $O(logn)$ per operation, $O(n*log(n)$) total || $O(n)$ || Exact || Deterministic || [https://dl.acm.org/doi/abs/10.1145/359131.359132 Time]
| [[Online 2-d Convex Hull, Preparata (2-dimensional Convex Hull, Online Convex Hull)|Online 2-d Convex Hull, Preparata]] || 1979 || $O(logn)$ per operation, $O(n*log(n)$) total || $O(n)$ || Exact || Deterministic || [https://dl.acm.org/doi/abs/10.1145/359131.359132 Time]

Latest revision as of 09:19, 10 April 2023

Description

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

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
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

References/Citation

https://ecommons.cornell.edu/handle/1813/6417

https://ecommons.cornell.edu/handle/1813/6417