  We consider the Minimum Convex Partition problem: Given a set 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 Minimum Convex Partition is NP-hard, and we give several
approximation algorithms, from an O(log OPT)-approximation running in
O(n^8)-time, where OPT denotes the minimum number of convex faces needed, to an
O(sqrt(n) log n)-approximation algorithm running in O(n^2)-time. We say that a
point set is k-directed if the (straight) lines containing at least three
points have up to k directions. We present an O(k)-approximation algorithm
running in n^O(k)-time. Those hardness and approximation results also holds for
the Minimum Convex Tiling problem, defined similarly but allowing the use of
Steiner points. The approximation results are obtained by relating the problem
to the Covering Points with Non-Crossing Segments problem. We show that this
problem is NP-hard, and present an FPT algorithm. This allows us to obtain a
constant-approximation FPT algorithm for the Minimum Convex Partition Problem
where the parameter is the number of faces.
