کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414765 681030 2013 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the number of crossing-free partitions
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the number of crossing-free partitions
چکیده انگلیسی

A partition of a point set in the plane is called crossing-free, if the convex hulls of the individual parts do not intersect. We prove that convex position of a planar set of n   points in general position minimizes the number of crossing-free partitions into 1, 2, 3, and n−3n−3, n−2n−2, n−1n−1, n   partition classes. Moreover, we show that for all n⩾5n⩾5 convex position of the underlying point set does not maximize the total number of crossing-free partitions.It is known that in convex position the number of crossing-free partitions into k   classes equals the number of partitions into n−k+1n−k+1 parts. This does not hold in general, and we mention a construction for point sets with significantly more partitions into few classes than into many.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 7, October 2013, Pages 879–893
نویسندگان
, ,