Metaheuristic approaches for the minimum dilation triangulation problem

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.