A fixed parameter algorithm for optimal convex partitions

We present a fixed-parameter algorithm for the Minimum Convex Partition and the Minimum Weight Convex Partition problem. The algorithm is based on techniques developed for the Minimum Weight Triangulation problem. On a set P of n points the algorithm runs in $O(2^k{k}^4{n}^3+n\log n)$ time. The parameter k is the number of points in P lying in the interior of the convex hull of P.