Criticism Of Hunting Minimum Weight Triangulation Edges
Andrej Ferko, Ľudovít Niepel, Tomáš Plachetka · 1996
. MinimumWeight Triangulation problem (MWT) is to find a set of edges of minimum total length that triangulates a given set of points in the plane. Although some properties of MWT have been proved and many heuristics proposed, polynomiality (and)/or NP-completness of MWT problem is still unsolved. The problem belongs to the few open problems from the book [GaJo]. In this paper we present results indicating that even very good approaches based on the local edge examination (like LMT-skeleton) fail to come close to the MWT for specially constructed set of points. Furthermore, we show a method how to construct a set of points for which MWT is unstable --- a slight displacement of a point in the input set causes significant change in the price of MWT. 1. Local MWT edge examination Up to now it is not known yet if there is a polynomial algorithm which finds the MWT for an arbitrary point set. Known polynomial algorithms related to MWT problem can be divided into two groups: 1. algorithms a...