关于平面点集的凸分解

On convex decompositions of points in the plane

给定处于一般位置的平面点集S,可将S划分为若干空凸子集使得这些子集的并形成一简单多边形P,并且S的每一个点均位于P的边界上.称P中这样的空凸k-子集为一k-胞腔.令f(S)为S的划分中所含胞腔的最小数,F(n)=max{f(S):S E2,|S|=n,无三点共线}.利用构造法将F(n)的下界改进为n+14.

Let S be a finite planar point set in general position. S can be partitioned into convex cells, such that the union of the cells forms a simple polygon P, and every point of S is on the boundary of P, such empty convex k-subset of P is called a k-cell. Let f(S) be the minimum number of cells obtained in such a partition of S. F(n)=max{f(S):S is a n-point planar set in general position}. The lower bound of F(n) is improved to n+14 .