Approximations on Minimum Weight Triangulations and Minimum Weight Pseudo-Triangulations Using Ant Colony Optimization Metaheuristic

• Autorzy: Dorzan M. G. , Gagliardi E. O. , Leguizamón M. G. , Pe�nalver G. H.
• Języki publikacji: EN

Abstrakty

EN

Globally optimal triangulations and pseudo-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) and Minimum Weight Pseudo- Triangulation (MWPT) problems of a given set of n points in the plane. This paper shows how the Ant Colony Optimization (ACO) metaheuristic can be used to find high quality triangulations and pseudo-triangulations of minimum weight. For the experimental study presented here we have created a set of instances for MWT and MWPT problems since no reference to benchmarks for these problems were found in the literature. Through the experimental evaluation, we assess the applicability of the ACO metaheuristic for MWT and MWPT problems considering greedy and Simulated Annealing algorithms.

Słowa kluczowe

EN

triangulation; pseudo-triangulation; minimum weight; computational geometry; ACO Metaheuristic

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 119, nr 1
• Strony: 1--27
• Opis fizyczny: Bibliogr. 59 poz., tab., wykr.

Twórcy

autor

Dorzan M. G.

autor

Gagliardi E. O.

autor

Leguizamón M. G.

autor

Pe�nalver G. H.

• Facultad de Ciencias Fýsico Matematicas y Naturales Universidad Nacional de San Luis San Luis, Argentina. Ejercito de Los Andes 950 - D5700HHW - San Luis - Argentina,

Bibliografia

• [1] CGAL, Computational Geometry Algorithms Library.
• [2] Aichholzer, O., Aurenhammer, F., Hainz, R.: New results on MWT subgraphs, Inf. Process. Lett., 69, March 1999, 215-219, ISSN 0020-0190.
• [3] Bäck, T., Fogel, D., Michalewicz, Z.: Handbook of evolutionary computation, Oxford Univ. Press, 1997.
• [4] Beirouti, R., Snoeyink, J.: Implementations of the LMT heuristic for minimum weight triangulation, Proceedings of the fourteenth annual symposium on Computational geometry, SCG '98, ACM, New York, NY, USA, 1998, ISBN 0-89791-973-4.
• [5] Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Comput. Surv., 35(3), 2003, 268-308.
• [6] Blum, C., Roli, A.: Hybrid Metaheuristics: An Introduction, in: Hybrid Metaheuristics, 2008, 1-30.
• [7] Brönnimann, H., Kettner, L., Pocchiola, M., Snoeyink, J.: Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm, SIAM J. Comput., 36, September 2006, 721-739, ISSN 0097-5397.
• [8] Canales, S.: M´etodos Heuristicos en Problemas Geom´etricos. Visibilidad, iluminacion y vigilancia, 2004.
• [9] Capp, K., Julstrom, B.: A weight-coded genetic algorithm for the minimum weight triangulation problem,SAC, 1998.
• [10] Černy, V.: Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimization Theory and Applications, 1985.
• [11] Cheng, S.-W., Xu, Y.-F.: Approaching the largest _-skeleton within a minimum weight triangulation, SCG '96: Proceedings of the twelfth annual symposium on Computational geometry, ACM, New York, NY, USA, 1996, ISBN 0-89791-804-5.
• [12] Davis, J., McCullagh, M.: Display and Analysis of Spatial Data, Wiley, 1975.
• [13] Dorigo, M., Sttzle, T.: Ant Colony Optimization, MIT Press, Cambridge, MA, 2004.
• [14] Dorzán, M., Gagliardi, E., Leguizamón, M., Hernández Peñalver, G.: Algoritmo ACO aplicado a la obtencion aproximada de Triangulaciones de PesoMinimo, XXXV Conferencia Latinoamericana de Informática, 2009, ISBN 857669247-3.
• [15] Dorzán, M., Gagliardi, E., Leguizamón, M., Hernández Peñalver, G.: Approximations on Minimum Weight Triangulations and Minimum Weight Pseudo-Triangulations using Ant Colony Optimization Metaheuristic, I Workshop on Emergent Computing (WEC). Jornadas Chilenas de Computación, 2009.
• [16] Dorzán, M., Gagliardi, E., Leguizamón, M., Hernández Peñalver, G.: Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic, Journal of Computer Science & Technology, 10, 2010, ISSN 1666-6038.
• [17] Dorzán, M., Gagliardi, E., Leguizamón, M., Hernández Peñalver, G.: Simulated Annealing aplicado a Triangulaciones y Pseudotriangulaciones de Peso Minimo, XVI Congreso Argentino de Ciencias de la Computación, 2010, ISBN 978-950-9474-49-9.
• [18] Dorzán, M., Gagliardi, E., Leguizamón, M., Hernández Peñalver, G.: Triangulaciones y Pseudotriangulaciones de Peso Minimo: resolución aproximada con Simulated Annealing, VII Jornadas de Matemática Discreta y Algoritmica. España, 2010, ISBN 978-84-693-3063-0.
• [19] Dorzán, M., Gagliardi, E., Leguizamón, M., Taranilla, M., Hernández Peñalver, G.: Algoritmos ACO aplicados a problemas geom´etricos de optimización, XIII Encuentros de Geometria Computacional, 2009, ISBN 978-84-9277-41-1.
• [20] Dorzán, M., Gagliardi, E., Palmero, P., Hernández Peñalver, G.: Una herramienta para la generación y visualización de Triangulaciones y Pseudotriangulaciones, XVI Congreso Argentino de Ciencias de la Computaci ón, 2010, ISBN 978-950-9474-49-9.
• [21] Düppe, R., Gottschalk, H.: Automatische Interpolation von Isolinien bei willkürlichen Stützpunkten, Allgemeine Vermessungsnachrichten, 77, 1970, 423-426.
• [22] Fang, K., Li, R., Sudjianto, A.: Design and Modeling for Computer Experiments (Computer Science & Data Analysis), Chapman & Hall/CRC, 2005, ISBN 1584885467.
• [23] Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
• [24] Geman, S., Geman, D.: Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, 1987, 564-584.
• [25] Gilbert, P.: New results in planar triangulations, Technical Report R-850, Univ. Illinois Coordinated Science Lab., 1979.
• [26] Gray, L., Martha, L., IngraLea, A.: Hypersingular intergrals in boundary element fracture analysis, 1990.
• [27] Gudmundsson, J., Levcopoulos, C.: Minimum weight pseudo-triangulations, Comput. Geom., 38(3), 2007, 139-153.
• [28] Ingber, A., Ingber, L.: Very Fast Simulated Re-Annealing, Mathematical Computer Modeling, 1989.
• [29] Keil, J. M.: Computing a subgraph of the minimum weight triangulation, Comput. Geom. Theory Appl., 4(1), 1994, 13-26, ISSN 0925-7721.
• [30] Kennedy, J., Eberhart, R.: Swarm Intelligence (The Morgan Kaufmann Series in Artificial Intelligence), 1st edition, Morgan Kaufmann, April 2001, ISBN 1558605959.
• [31] Kirkpatrick, D.: A Note on Delaunay and Optimal Triangulations, Inf. Process. Lett., 10(3), 1980, 127-128.
• [32] Kirkpatrick, D. G., Radke, J. D.: A Framework for Computational Morphology, in: Computational Geometry (G. T. Toussaint, Ed.), NH, Amst, 1985, 217-248.
• [33] Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimization by Simulated Annealing, Science, 220, 1983, 671-680.
• [34] Klincsek, G.: Minimal triangulations of polygonal domains, Ann. Disc. Math., 9, 1980, 121-123.
• [35] Kolingerová, I., Ferko, A.: Multicriteria-optimized triangulations, The Visual Computer, 17(6), 2001, 380-395.
• [36] Levcopoulos, C.: An Ω(√(n)) Lower Bound for the Nonoptimality of the Greedy Triangulation, Inf. Process. Lett., 25(4), 1987, 247-251.
• [37] Levcopoulos, C., Krznaric, D.: Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation, J. Algorithms, 27(2), 1998, 303-338.
• [38] Lloyd, E.: On triangulations of a set of points in the plane, "Proc. 18th IEEE Symp. Found. Comp. Sci., 1977.
• [39] Manacher, G., Zobrist, A.: Neither the Greedy Nor the Delaunay Triangulation of a Planar Point Set Approximates the Optimal Triangulation, Inf. Process. Lett., 9(1), 1979, 31-34.
• [40] Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E.: Equation of State Calculations by Fast Computing Machines, Journal of Chemical Physics, 21, 1953, 1087-1092.
• [41] Michalewicz, Z., Fogel, D.: How to Solve It: Modern Heuristics, Springer, 2004.
• [42] Mulzer,W., Rote, G.: Minimum weight triangulation is NP-hard, In Proc. 22nd Annu. ACM Sympos. Comput. Geom, ACM Press, 2006.
• [43] Nilsson, B.,Wood, D.: OptimumWatchmen Routes in Spiral Polygons. Proceedings of the Second Canadian Conference in Computational Geometry, 1990.
• [44] Osman, I., Kelly, J.: Meta-heuristics: Theory and Applications, Kluwer academic publishers, 1996.
• [45] Plaisted, D., Hong, J.: A heuristic triangulation algorithm, J. Algorithms, 8, 1987, 405-437.
• [46] Pocchiola, M., Vegter, G.: Pseudo-Triangulations: Theory and Applications, Symposium on Computational Geometry, 1996.
• [47] Project, C. S. E.: Mathematical Optimization, 1995.
• [48] Qin, K., Wang, W., Gong, M.: A genetic algorithm for the minimum weight triangulation, In Proceedings of 1997 IEEE International Conference on Evolutionary Computation, 1997.
• [49] Remy, J., Steger, A.: A quasi-polynomial time approximation scheme for minimum weight triangulation., Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, ACM, 2006, ISBN 1-59593-134-1.
• [50] Rote, G., Santos, F., Streinu, I.: Pseudo-triangulations - a survey, Contemporary Mathematics, American Mathematical Society, December 2008.
• [51] Rote, G., Wang, C., Wang, L., Xu, Y.: On constrained minimum pseudotriangulations, In Proc. 9th Intern. Comp. Comb. Conf., 2003.
• [52] Sen, S., Zheng, S.: Near-optimal triangulation of a point set by simulated annealing, SAC '92: Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing, ACM, New York, NY, USA, 1992, ISBN 0-89791-502-X.
• [53] Shamos, M., Hoey, D.: Closest-point problems, Proc. 16th IEEE Symp. Foundations of Comp. Science, 1975.
• [54] Szu, H., Hartley, R.: Fast simulated annealing. Physics Letters A., 1987.
• [55] T., B.-B.: SPOT: Sequential Parameter Optimization Toolbox, http://www.gm.fhkoeln. de/campus/personen/lehrende/thomas.bartz-beielstein/00489/.
• [56] T., B.-B.: Experimental Research in Evolutionary Computation: The New Experimentalism (Natural Computing Series), Springer, 2006.
• [57] Wu, Y., Wainwright, R.: Near-optimal triangulation of a point set using Genetic Algorithms, Proceedings of the Seventh Oklahoma Conference on AI., 1993.
• [58] Yao, X.: A new simulated annealing algorithm, International Journal of Computer Mathematics, 1995, 161-168.
• [59] Yoeli, P.: Compilation of data for computer-assisted relief cartography, 1975.