کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4632144 1340637 2010 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Convex hull properties and algorithms
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
Convex hull properties and algorithms
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 216, Issue 11, 1 August 2010, Pages 3209–3218
نویسندگان
, , , , ,