TITLE:
On Constructing Approximate Convex Hull
AUTHORS:
M. Zahid Hossain, M. Ashraful Amin
KEYWORDS:
Convex Hull; Approximation Algorithm; Computational Geometry; Linear Time
JOURNAL NAME:
American Journal of Computational Mathematics,
Vol.3 No.1A,
April
30,
2013
ABSTRACT: The algorithms of convex hull have been extensively studied in literature, principally because of their wide range of applications in different areas. This article presents an efficient algorithm to construct approximate convex hull from a set of n points in the plane in O(n+k) time, where k is the approximation error control parameter. The proposed algorithm is suitable for applications preferred to reduce the computation time in exchange of accuracy level such as animation and interaction in computer graphics where rapid and real-time graphics rendering is indispensable.