On the Number of Empty Convex Quadrilaterals for
a Planar Point Set

Liping Wu
College of Mathematics and Computer Science, Hebei Normal University,
Shijiazhuang 050016,
P.R.China


Abstract    
In 2001 K. Hosono and M. Urabe considered the problem of the number of disjoint empty convex k-gons in a planar point set for a fixed k. They mainly studied the case k=4 and proved F4(9)=2, . In this paper, we remove the restriction of disjointness and consider a related problem: how many empty convex k-gons can be constructed in a planar point set for a fixed k? We mainly study case of k=4 as well and obtain some meaningful results. Let P be a set of n points in the plane with no three collinear, that is, P is in general position. We call a partition of P an {\it empty convex partition} if P is partitioned into subsets S1, S2, ..., St; such that each CH(Si) is an |Si|-gon for every i, and CH(Si) is empty, where CH denotes the convex hull. Let k be a positive integer and be the number of empty convex k-gons in an empty convex partition of P. We denote

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

In this paper, we obtain the following results :
G4(5)=1, G4(9)=2, G4(13)=3, G4(17)=4
By using these results we show that for a set of 38 points we can construct 9 empty convex quadrilaterals and so we obtain In the proof, we make use of the following lemma proved by K.Hosono and M.Urabe: For any set of 2m+4 points in the plane, no three collinear, we can divide the plane into three disjoint convex regions such that one contains a convex quadrilateral and the others contain m points each, where m is a positive integer.
Moreover, for , we get the following better bound: .