Globally Optimal Triangulations of Minimum Weight Using Ant Colony Optimization Metaheuristic

Date Added: Jun 2010
Format: PDF

Globally optimal triangulations are difficult to be found by deterministic methods as, for most type of criteria, no polynomial algorithm is known. In this paper, the authors consider the Minimum Weight Triangulation (MWT) problem of a given set of n points in the plane. Their aim is to show how the Ant Colony Optimization (ACO) metaheuristic can be used to search for globally optimal triangulations of minimum weight. They present an experimental study for a set of instances for MWT problem. They create these instances since no reference to benchmarks for this problem were found in the literature.