کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414765 | 681030 | 2013 | 15 صفحه PDF | دانلود رایگان |

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.
Journal: Computational Geometry - Volume 46, Issue 7, October 2013, Pages 879–893