L. Kavan, I. Kolingerova, and J. Zara (Czech Republic)
convex hull, approximation, linear time
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.
Important Links:
Go Back
