Before revision:  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:  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 }log n)-approximation algorithm running in quadratic time. The latter result is obtained by relating the problem to another geometric problem: Given a set of points P, cover P with a minimum number of lines. A constant-factor approximation algorithm was shown for Minimum Convex Partition by Knauer and Spillner, for point sets where no three points are on a line (SWAT 2006). This restriction is crucial for the algorithm to work. The complexity of the problem under this restriction remains open .