期刊名称：American Journal of Computational Mathematics
印刷版ISSN：2161-1203
电子版ISSN：2161-1211
出版年度：2013
卷号：3
期号：1A
页码：11-17
DOI：10.4236/ajcm.2013.31A003
出版社：Scientific Research Publishing
摘要：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.
关键词：Convex Hull; Approximation Algorithm; Computational Geometry; Linear Time
