کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414249 680861 2015 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the minimum number of mutually disjoint holes in planar point sets
ترجمه فارسی عنوان
در حداقل تعداد حفره های متقاطع در مجموعه نقطه های مسطح
کلمات کلیدی
پارتیشن یک مجموعه نقطه مسطح، حفره های متقاطع (چند ضلعی محدب خالی)، هندسه گسسته
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let P be a set of n points in general position in the plane. In 1996, Urabe considered a partition of P   into subsets S1∪⋯∪SlS1∪⋯∪Sl such that each SiSi forms a hole (or an empty convex polygon) of P   and these holes are mutually disjoint. Let f(P)f(P) be the minimum number of holes over all such partitions of P   and F(n)=max{f(P)}F(n)=max{f(P)} over all sets P of n   points. Then the current best bounds are given by ⌈n+14⌉≤F(n)≤⌈5n18⌉. In this paper, we prove that F(n)≤⌈n4⌉+1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 48, Issue 9, October 2015, Pages 661–672
نویسندگان
,