The minimum weight triangulation problem with few inner points

We look at the computational complexity of 2-dimensional geometric optimization problems on a finite point set with respect to the number of inner points (that is, points in the interior of the convex hull). As a case study, we consider the minimum weight triangulation problem. Finding a minimum weight triangulation for a set of n points in the plane is not known to be NP-hard nor solvable in polynomial time, but when the points are in convex position, the problem can be solved in O(n³) time by dynamic programming. We extend the dynamic programming approach to the general problem and describe an exact algorithm which runs in O(6^kn⁵logn) time where n is the total number of input points and k is the number of inner points. If k is taken as a parameter, this is a fixed-parameter algorithm. It also shows that the problem can be solved in polynomial time if k=O(logn). In fact, the algorithm works not only for convex polygons, but also for simple polygons with k inner points.