Before revision: Given a point set P , are k closed convex polygons sufficient to partition the convex hull of P , such that the interior of a convex set contains no point in P? What if the vertices of these polygons are constrained to be points of P ? We show that the first decision problem is NP-hard, and the second NP-complete } .
After revision: Given a point set P , are k closed convex polygons sufficient to partition the convex hull of P of n points in the plane, draw a plane graph G on P, with positive minimum degree, such that G partitions the convex hull of P into a minimum number of convex faces. We show that the first decision problem is NP-hard, and the second NP-complete } .