FAST APPROXIMATION OF CONVEX HULL
Ladislav Kavan, Ivana Kolingerová, Jiřı́ Žára · 2014
The construction of a planar convex hull is an essential op-eration in computational geometry. It has been proven that the time complexity of an exact solution is Ω(NlogN). In this paper, we describe an algorithm with time complexity O(N + k2), where k is parameter controlling the approxi-mation quality. This is beneficial for applications process-ing a large number of points without necessity of an exact solution. A formula for upper bound of the approximation error is presented. KEY WORDS convex hull, approximation, linear time 1