Optimal convex partitions of point sets with few inner points.
Andreas Spillner · Canadian Conference on Computational Geometry · 2005
We present a fixed-parameter algorithm for the Minimum Convex Partition and the Minimum Weight Convex Partition problem. On a set P of n points the algorithm runs in O(2kn +n logn) time. The parameter k is the number of points in P lying in the interior of the convex hull of P .