Repositorio de producción científica de la Universidad de Sevilla

Metaheuristic approaches for the minimum dilation triangulation problem


Advanced Search
Opened Access Metaheuristic approaches for the minimum dilation triangulation problem
Show item statistics
Export to
Author: Dorzán, María Gisela
Leguizamón, Mario Guillermo
Mezura Montes, Efrén
Hernández Peñalver, Gregorio
Coordinator/Director: Díaz Báñez, José Miguel
Garijo Royo, Delia
Márquez Pérez, Alberto
Urrutia Galicia, Jorge
Date: 2013
Published in: XV Spanish Meeting on Computational Geometry (2013), p 35-38
Document type: Presentation
Abstract: We focus on the development of approximated algorithms to find high quality triangulations of minimum dilation because the complexity status of the Minimum Dilation Triangulation problem for a general point set is unknown. We propose an operator to generate the neigborhood which is used in different algorithms: Local Search, Iterated Local Search, and Simulated Annealing. Besides, an algorithm called Random Local Search is presented where good and bad solutions are accepted using the previous mentioned operator. We use the Sequential Parameter Optimization method for tuning the parameters of the SA algorithm. We compare our results with the only available algorithm found in the literature that uses the obstacle value to sort the edges in the constructive process. Through the experimental evaluation and statistical analysis, we assess the performance of the proposed algorithms using this operator.
Size: 699.0Kb
Format: PDF


See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)