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 ( 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.
68w40