دانلود مقاله ISI انگلیسی شماره 89664
ترجمه فارسی عنوان مقاله

نقاط پوشش با مجموعه های محدب حداقل اندازه

عنوان انگلیسی
Covering points with convex sets of minimum size
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
89664 2018 10 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Theoretical Computer Science, Volume 718, 29 March 2018, Pages 14-23

ترجمه کلمات کلیدی
امتیازات پوشش مجموعه های محدب، بدنه محدب، حوزه، محدوده هندسه محاسباتی،
کلمات کلیدی انگلیسی
Covering points; Convex sets; Convex hulls; Area; Perimeter; Computational geometry;
پیش نمایش مقاله
پیش نمایش مقاله  نقاط پوشش با مجموعه های محدب حداقل اندازه

چکیده انگلیسی

For a set P of n points in the plane, we present algorithms for finding two bounded convex sets that cover P such that the total area or perimeter of the convex sets is minimized in O(n4log⁡n) and O(n2log⁡n) time, respectively. The former is the first result for minimum total area, and the latter is an improvement on the fastest previous algorithm for minimum total perimeter, which runs in O(n3) time [24]. We also extend our algorithms to find k⩾2 convex sets minimizing area in O(n2k(k−1)log⁡n) time. The algorithms can be applied to detect road intersections from the GPS trajectories of moving vehicles for automated map generation or partial clustering.