On a partition into convex polygons Original Research Article

In this paper we study the problem of partitioning point sets in the plane so that each equivalence class is a convex polygon with some conditions on the intersection properties of such sets. Let P be a set of n points in the plane. We define f(P) to be the minimum number of sets in a partition into disjoint convex polygons of P and F(n) as the maximum off(P), over all sets P of n points. We establish lower and upper bounds for F(n). We also estimate the maximum of the minimum number of sets in a partition into empty convex polygons, over all sets of n points. Finally, we consider the maximum of the minimum number of convex polygons which cover the n points set P, over all sets P of n points.