Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic

Globally optimal triangulations are difficult to be found by deterministic methods as, for most type of criteria, no polynomial algorithm is known. In this work, we consider the Minimum Weight Triangulation (MWT) problem of a given set of n points in the plane. Our aim is to show how the Ant Colony...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Dorzán, María Gisela, Gagliardi, Edilma Olinda, Leguizamón, Mario Guillermo, Hernández Peñalver, Gregorio
Formato: Articulo
Lenguaje:Inglés
Publicado: 2010
Materias:
Ciencias Informáticas
Computational Geometry and Object Modeling
Heuristic methods
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/9668
http://journal.info.unlp.edu.ar/wp-content/uploads/JCST-Jun10-1.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-9668
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Computational Geometry and Object Modeling
Heuristic methods
spellingShingle Ciencias Informáticas
Computational Geometry and Object Modeling
Heuristic methods
Dorzán, María Gisela
Gagliardi, Edilma Olinda
Leguizamón, Mario Guillermo
Hernández Peñalver, Gregorio
Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic
topic_facet Ciencias Informáticas
Computational Geometry and Object Modeling
Heuristic methods
description Globally optimal triangulations are difficult to be found by deterministic methods as, for most type of criteria, no polynomial algorithm is known. In this work, we consider the Minimum Weight Triangulation (MWT) problem of a given set of n points in the plane. Our aim is to show how the Ant Colony Optimization (ACO) metaheuristic can be used to search for globally optimal triangulations of minimum weight. We present an experimental study for a set of instances for MWT problem. We create these instances since no reference to benchmarks for this problem were found in the literature. We assess through the experimental evaluation the applicability of the ACO metaheuristic for MWT problem.
format Articulo
Articulo
author Dorzán, María Gisela
Gagliardi, Edilma Olinda
Leguizamón, Mario Guillermo
Hernández Peñalver, Gregorio
author_facet Dorzán, María Gisela
Gagliardi, Edilma Olinda
Leguizamón, Mario Guillermo
Hernández Peñalver, Gregorio
author_sort Dorzán, María Gisela
title Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic
title_short Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic
title_full Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic
title_fullStr Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic
title_full_unstemmed Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic
title_sort globally optimal triangulations of minimum weight using ant colony optimization metaheuristic
publishDate 2010
url http://sedici.unlp.edu.ar/handle/10915/9668
http://journal.info.unlp.edu.ar/wp-content/uploads/JCST-Jun10-1.pdf
work_keys_str_mv AT dorzanmariagisela globallyoptimaltriangulationsofminimumweightusingantcolonyoptimizationmetaheuristic
AT gagliardiedilmaolinda globallyoptimaltriangulationsofminimumweightusingantcolonyoptimizationmetaheuristic
AT leguizamonmarioguillermo globallyoptimaltriangulationsofminimumweightusingantcolonyoptimizationmetaheuristic
AT hernandezpenalvergregorio globallyoptimaltriangulationsofminimumweightusingantcolonyoptimizationmetaheuristic
bdutipo_str Repositorios
_version_ 1764820492364021760

Ejemplares similares