Approximations on minimum weight pseudo-triangulation problem using ant colony optimization

Hernández Peñalver, Gregorio and Gagliardi, Edilma Olinda and Dorzán, M. Gisela and Leguizamón, Guillermo (2011). Approximations on minimum weight pseudo-triangulation problem using ant colony optimization. In: "30th International Conference of the Chilean", 9-11 Nov. 2011, Curico, Chile. ISBN 978-0-7695-4689-6.

Description

Title: Approximations on minimum weight pseudo-triangulation problem using ant colony optimization
Author/s:
  • Hernández Peñalver, Gregorio
  • Gagliardi, Edilma Olinda
  • Dorzán, M. Gisela
  • Leguizamón, Guillermo
Item Type: Presentation at Congress or Conference (Article)
Event Title: 30th International Conference of the Chilean
Event Dates: 9-11 Nov. 2011
Event Location: Curico, Chile
Title of Book: Computer Science Society (SCCC), 2011 30th International Conference of the Chilean
Date: 2011
ISBN: 978-0-7695-4689-6
Subjects:
Freetext Keywords: Pseudo-triangulation, Minimum weight, Computational Geometry, ACO Metaheuristic, Seudotriangulación, Tamaño mínimo, Geometría computacional.
Faculty: Facultad de Informática (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (155kB) | Preview

Abstract

In this work, we consider the Minimum Weight Pseudo-Triangulation (MWPT) problem of a given set of n points in the plane. Globally optimal pseudo-triangulations with respect to the weight, as optimization criteria, are difficult to be found by deterministic methods, since no polynomial algorithm is known. We show how the Ant Colony Optimization (ACO) metaheuristic can be used to find high quality pseudo-triangulations of minimum weight. We present the experimental and statistical study based on our own set of instances since no reference to benchmarks for these problems were found in the literature. Throughout the experimental evaluation, we appraise the ACO metaheuristic performance for MWPT problem.

More information

Item ID: 19305
DC Identifier: http://oa.upm.es/19305/
OAI Identifier: oai:oa.upm.es:19305
Official URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6363403
Deposited by: Memoria Investigacion
Deposited on: 26 Sep 2013 14:52
Last Modified: 21 Apr 2016 17:34
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM