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(6 ^{k}n^{5}*log