ON A PARTITION INTO CONVEX POLYGONS

Authors
Citation
M. Urabe, ON A PARTITION INTO CONVEX POLYGONS, Discrete applied mathematics, 64(2), 1996, pp. 179-191
Citations number
4
Categorie Soggetti
Mathematics,Mathematics
Volume
64
Issue
2
Year of publication
1996
Pages
179 - 191
Database
ISI
SICI code
Abstract
In this paper we study the problem of partitioning point sets in the p lane so that each equivalence class is a convex polygon with some cond itions 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 max imum of f(P), over all sets P of n points. We establish lower and uppe r 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 conv ex polygons which cover the n points set P, over all sets P of n point s.