On Constructing Approximate Convex Hull

• 作者: M. Ashraful Amin M. Zahid Hossain
• 来源期刊: 美国计算数学期刊(英文)
• 学科: 数学
• 关键词: CONVEX HULL APPROXIMATION Algorithm COMPUTATIONAL Geometry Linear Time
• 年，卷（期）: mgjssxqkyw_2013,（1）
• 页码范围: 11-17
• 页数: 7页
• 分类号: O1

摘要

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.