Andreas Spillner: A Faster Algorithm for the Minimum Weight Triangulation Problem with Few Inner Points

We consider the Minimum Weight Triangulation problem, that is the problem of computing a triangulation of a given set P of n points in the plane such that the total edge length is minimum. For this problem neither a polynomial time algorithm is known nor is the problem known to be NP-hard. However Hoffmann and Okamoto presented a fixed-parameter algorithm running in O(6kn5logn) time, where the parameter k is the number of points in P lying in the interior of the convex hull of P. We will show that the approach of Hoffmann and Okamoto can be improved to yield an algorithm running in O(2kkn3 + n3) time.