Ponencia
Metaheuristic approaches for the minimum dilation triangulation problem
Autor/es | Dorzán, María Gisela
Leguizamón, Mario Guillermo Mezura Montes, Efrén Hernández Peñalver, Gregorio |
Coordinador/Director | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II |
Fecha de publicación | 2013 |
Fecha de depósito | 2017-05-18 |
Publicado en |
|
Resumen | 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 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. |
Identificador del proyecto | 22/F014
ComPoSe IP04 EUI-EURC-2011-4306 |
Cita | Dorzán, M.G., Leguizamón, M.G., Mezura Montes, E. y Hernández Peñalver, G. (2013). Metaheuristic approaches for the minimum dilation triangulation problem. En XV Spanish Meeting on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Metaheuristic approaches for the ... | 699.0Kb | [PDF] | Ver/ | |