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(k2k4n3+nlogn)O(2kk4n3+nlogn) time. The parameter k is the number of points in P lying in the interior of the convex hull of P.