Some Results on the Partition Problems of Finite
Planar Point Sets


Yaling Wang and Xuefen Liu
College of Mathematics, Hebei Normal University,
Shijiazhuang 050016, P.R. China

Abstract

Let P be a set of finite points in the plane, no three collinear. A convex polygon determined by a subset of P is called an empty polygon if no points of P lie in the interior of its convex hull. More generally, we call a closed region D empty, denoted by D ,if no points of P lie in the interior of D.
A partition of P is called a convex partition if P is partitioned by k subsets S1 , S2 ,..., Sk, such that each CH (Si ) is an |Si |-gon, where CH( Si ) denotes the convex hull of Si . If CH( Si ) CH( Sj ) = for any pair of indices ( i j ), then this partition is called a disjoint partition of P; if CH( Si ) for each i, we call this partition an empty partition of P. Let k be a positive integer and be the number of convex k-gons in a partition of P. Let be the number of convex polygons in a partition of P. We denote

fk(P) = : max{:is a disjiont partition of P}
Fk(n) = :min{fk(P):|P|=n}
f(P) = : min{:is a disjiont partition of P}
F(n) = :max{f(P):|P|=n}
g(P) = : min{:is an empty partition of P}
G(n) = :max{g(P):|P|=n}


Hosono and Urabe studied these functions, and we improve the upper bound of G(n). Moreover, we define

gk(P) = : max{:is an empty partition of P}
Gk(n) = :min{gk(P):|P|=n}


and obtain the following results: