Kiyoshi Hosono and Masatsugu Urabe

Erdõs [1] asked the following combinatorial geometry problem: Find the smallest integer n(k) such that any set of n(k) points in the plane, no three collinear, contains the vertices of a convex k-gon, whose interior contains no point of the set. Such a convex k-gon is said to be empty. Klein [2] found n(4)=5, and n(5)=10 was determined by Harborth [3]. Horton [4] showed that n(k) does not exist for k

7. The value of n(6) is still open. We consider a related problem: Let n(k,l) be the smallest integer such that any set of n(k,l) points in the plane, no three collinear, contains both an empty convex k-gon and an empty convex l-gon, which do not intersect. Clearly, n(3,3)=6 and n(k,7)= \infty$. A partition of a given planar point set, no three collinear, is said to be disjoint if each subset is empty convex and ch(S_i) ch(S_j)

for every pair of subsets S_i and S_j, where ch stands for the convex hull. When we studied disjoint partitions, we found n(3,4)=7 and n(4,4)=9 in [7] and [5], respectively. And in [6], we introduced this concept and estimated the several values; n(3,5)=10, 12

n(4,5)

14, 16

n(5,5)

20. In this talk, we give the improved values for this function.