کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4632144 | 1340637 | 2010 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Convex hull properties and algorithms Convex hull properties and algorithms](/preview/png/4632144.png)
Convex hull (CH) is widely used in computer graphic, image processing, CAD/CAM, and pattern recognition. We investigate CH properties and derive new properties: (1) CH vertices’ coordinates monotonically increase or decrease, (2) The edge slopes monotonically decrease. Using these properties, we proposed two algorithms, i.e., CH algorithm for planar point set, and CH algorithm for two available CHs. The main ideas of the proposed algorithms are as follows. A planar point set is divided into several subsets by the extreme points, and vertices in these subsets are then separately calculated. During the computation, the CH properties are used to eliminate concave points. This can reduce the computational cost and then improves the speed. Our first algorithm can extract CH with O(nlogn)O(nlogn) time, which is the lower bound of planar CH extraction, and the second algorithm can obtain CH with O(m+n)O(m+n) time at the worst case.
Journal: Applied Mathematics and Computation - Volume 216, Issue 11, 1 August 2010, Pages 3209–3218