Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC. Authors must sign a non-exclusive distribution agreement after article acceptance.
Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic
Keywords:
Triangulation, Minimum Weight Triangulation, Computational Geometry, ACO MetaheuristicAbstract
Globally optimal 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) problem of a given set of n points in the plane. Our aim is to show how the Ant Colony Optimization (ACO) metaheuristic can be used to search for globally optimal triangulations of minimum weight. We present an experimental study for a set of instances for MWT problem. We create these instances since no reference to benchmarks for this problem were found in the literature. We assess through the experimental evaluation the applicability of the ACO metaheuristic for MWT problem.
Downloads
Download data is not yet available.
References
1] Cgal, computational geometry algorithms library.
[2] T. Bäck, D. Fogel, and Z. Michalewicz. Handbook of evolutionary computationm. Oxford Univ. Press, 1997.
[3] K. Capp and B. Julstrom. A weight-coded genetic algorithm for the minimum weight triangulation problem. In SAC, pages 327–331, 1998.
[4] Siu-Wing Cheng and Yin-Feng Xu. Approaching the largest β-skeleton within a minimum weight triangulation. In SCG ’96: Proceedings of the twelfth annual symposium on Computational geometry, pages 196–203, New York, NY, USA, 1996. ACM.
[5] M. Dorigo and T. Sttzle. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
[6] M. Dorzán, E. Gagliardi, Leguizamón, and G. M., Hernández Penalver. Algoritmo aco aplicado a la obtención aproximada de triangulaciones de peso mínimo. In XXXV Conferencia Latinoamericana de Informática, 2009.
[7] M. Dorzán, E. Gagliardi, M. Leguizamón, M. Taranilla, and G. Hernández Penálver. Algoritmos aco aplicados a problemas geométricos de optimización. In XIII Encuentros de Geometría Computacional, 2009.
[8] R. Düppe and H. Gottschalk. Automatische interpolation von isolinien bei willkürlichen stützpunkten. Allgemeine Vermessungsnachrichten, 77:423–426, 1970.
[9] Kai-Tai Fang, Runze Li, and Agus Sudjianto. Design and Modeling for Computer Experiments (Computer Science & Data Analysis). Chapman & Hall/CRC, 2005.
[10] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
[11] P. Gilbert. New results in planar triangulations. Technical Report R–850, Univ. Illinois Coordinated Science Lab., 1979.
[12] J. Mark Keil. Computing a subgraph of the minimum weight triangulation. Comput. Geom. Theory Appl., 4(1):13–26, 1994.
[13] J. Kennedy and R. Eberhart. Swarm Intelligence (The Morgan Kaufmann Series in Artificial Intelligence). Morgan Kaufmann, 1st edition, April 2001.
[14] D. Kirkpatrick. A note on delaunay and optimal triangulations. Inf. Process. Lett., 10(3):127–128, 1980.
[15] David G. Kirkpatrick and John D. Radke. A framework for computational morphology. In G. T. Toussaint, editor, Computational Geometry, pages 217–248. NH, Amst, 1985.
[16] G. Klincsek. Minimal triangulations of polygonal domains. Ann. Disc. Math., 9:121–123, 1980.
[17] I. Kolingerová and A. Ferko. Multicriteria-optimized triangulations.The Visual Computer, 17(6):380–395, 2001.
[18] C. Levcopoulos. An ω(√ (n)) lower bound for the nonoptimality of the greedy triangulation. Inf. Process. Lett., 25(4):247–251, 1987.
[19] C. Levcopoulos and D. Krznaric. Quasi-greedy triangulations approximating the minimum weight triangulation. J. Algorithms, 27(2):303–338, 1998.
[20] E. Lloyd. On triangulations of a set of points in the plane. In ”Proc. 18th IEEE Symp. Found. Comp. Sci., pages 228–240, 1977.
[21] G. Manacher and A. Zobrist. Neither the greedy nor the delaunay triangulation of a planar point set approximates the optimal triangulation. Inf. Process. Lett., 9(1):31–34, 1979.
[22] Z. Michalewicz and D. Fogel. How to Solve It: Modern Heuristics. Springer, 2004.
[23] W. Mulzer and G. Rote. Minimum weight triangulation is np-hard. In In Proc. 22nd Annu. ACM Sympos. Comput. Geom, pages 1–10. ACM Press, 2006.
[24] I. Osman and J. Kelly. Meta-heuristics: Theory and Applications. Kluwer academic publishers, 1996.
[25] D. Plaisted and J. Hong. A heuristic triangulation algorithm. J. Algorithms, 8:405–437, 1987.
[26] K. Qin, W. Wang, and M. Gong. A genetic algorithm for the minimum weight triangulation. In In Proceedings of 1997 IEEE International Conference on Evolutionary Computation, 1997.
[27] J. Remy and A. Steger. A quasi-polynomial time approximation scheme for minimum weight triangulation. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006. ACM, 2006.
[28] S. Sen and S. Zheng. Near-optimal triangulation of a point set by simulated annealing. In SAC ’92: Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing, pages 1000–1008, New York, NY, USA, 1992. ACM.
[29] M. Shamos and D. Hoey. Closest-point problems. In Proc.16th IEEE Symp. Foundations of Comp. Science, pages 151–162, 1975.
[30] Bartz-Beielstein T. Spot: Sequential parameter optimization toolbox. http://www.gm.fhkoeln.de/campus/personen/lehrende/thomas.bartzbeielstein/00489/.
[31] Bartz-Beielstein T. Experimental Research in Evolutionary Computation: The New Experimentalism (Natural Computing Series). Springer, 2006.
[32] Y. Wu and R. Wainwright. Near-optimal triangulation of a point set using genetic algorithms. In Proceedings of the Seventh Oklahoma Conference on AI., 1993
[2] T. Bäck, D. Fogel, and Z. Michalewicz. Handbook of evolutionary computationm. Oxford Univ. Press, 1997.
[3] K. Capp and B. Julstrom. A weight-coded genetic algorithm for the minimum weight triangulation problem. In SAC, pages 327–331, 1998.
[4] Siu-Wing Cheng and Yin-Feng Xu. Approaching the largest β-skeleton within a minimum weight triangulation. In SCG ’96: Proceedings of the twelfth annual symposium on Computational geometry, pages 196–203, New York, NY, USA, 1996. ACM.
[5] M. Dorigo and T. Sttzle. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
[6] M. Dorzán, E. Gagliardi, Leguizamón, and G. M., Hernández Penalver. Algoritmo aco aplicado a la obtención aproximada de triangulaciones de peso mínimo. In XXXV Conferencia Latinoamericana de Informática, 2009.
[7] M. Dorzán, E. Gagliardi, M. Leguizamón, M. Taranilla, and G. Hernández Penálver. Algoritmos aco aplicados a problemas geométricos de optimización. In XIII Encuentros de Geometría Computacional, 2009.
[8] R. Düppe and H. Gottschalk. Automatische interpolation von isolinien bei willkürlichen stützpunkten. Allgemeine Vermessungsnachrichten, 77:423–426, 1970.
[9] Kai-Tai Fang, Runze Li, and Agus Sudjianto. Design and Modeling for Computer Experiments (Computer Science & Data Analysis). Chapman & Hall/CRC, 2005.
[10] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
[11] P. Gilbert. New results in planar triangulations. Technical Report R–850, Univ. Illinois Coordinated Science Lab., 1979.
[12] J. Mark Keil. Computing a subgraph of the minimum weight triangulation. Comput. Geom. Theory Appl., 4(1):13–26, 1994.
[13] J. Kennedy and R. Eberhart. Swarm Intelligence (The Morgan Kaufmann Series in Artificial Intelligence). Morgan Kaufmann, 1st edition, April 2001.
[14] D. Kirkpatrick. A note on delaunay and optimal triangulations. Inf. Process. Lett., 10(3):127–128, 1980.
[15] David G. Kirkpatrick and John D. Radke. A framework for computational morphology. In G. T. Toussaint, editor, Computational Geometry, pages 217–248. NH, Amst, 1985.
[16] G. Klincsek. Minimal triangulations of polygonal domains. Ann. Disc. Math., 9:121–123, 1980.
[17] I. Kolingerová and A. Ferko. Multicriteria-optimized triangulations.The Visual Computer, 17(6):380–395, 2001.
[18] C. Levcopoulos. An ω(√ (n)) lower bound for the nonoptimality of the greedy triangulation. Inf. Process. Lett., 25(4):247–251, 1987.
[19] C. Levcopoulos and D. Krznaric. Quasi-greedy triangulations approximating the minimum weight triangulation. J. Algorithms, 27(2):303–338, 1998.
[20] E. Lloyd. On triangulations of a set of points in the plane. In ”Proc. 18th IEEE Symp. Found. Comp. Sci., pages 228–240, 1977.
[21] G. Manacher and A. Zobrist. Neither the greedy nor the delaunay triangulation of a planar point set approximates the optimal triangulation. Inf. Process. Lett., 9(1):31–34, 1979.
[22] Z. Michalewicz and D. Fogel. How to Solve It: Modern Heuristics. Springer, 2004.
[23] W. Mulzer and G. Rote. Minimum weight triangulation is np-hard. In In Proc. 22nd Annu. ACM Sympos. Comput. Geom, pages 1–10. ACM Press, 2006.
[24] I. Osman and J. Kelly. Meta-heuristics: Theory and Applications. Kluwer academic publishers, 1996.
[25] D. Plaisted and J. Hong. A heuristic triangulation algorithm. J. Algorithms, 8:405–437, 1987.
[26] K. Qin, W. Wang, and M. Gong. A genetic algorithm for the minimum weight triangulation. In In Proceedings of 1997 IEEE International Conference on Evolutionary Computation, 1997.
[27] J. Remy and A. Steger. A quasi-polynomial time approximation scheme for minimum weight triangulation. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006. ACM, 2006.
[28] S. Sen and S. Zheng. Near-optimal triangulation of a point set by simulated annealing. In SAC ’92: Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing, pages 1000–1008, New York, NY, USA, 1992. ACM.
[29] M. Shamos and D. Hoey. Closest-point problems. In Proc.16th IEEE Symp. Foundations of Comp. Science, pages 151–162, 1975.
[30] Bartz-Beielstein T. Spot: Sequential parameter optimization toolbox. http://www.gm.fhkoeln.de/campus/personen/lehrende/thomas.bartzbeielstein/00489/.
[31] Bartz-Beielstein T. Experimental Research in Evolutionary Computation: The New Experimentalism (Natural Computing Series). Springer, 2006.
[32] Y. Wu and R. Wainwright. Near-optimal triangulation of a point set using genetic algorithms. In Proceedings of the Seventh Oklahoma Conference on AI., 1993
Downloads
Published
2010-06-01
How to Cite
Dorzán, M. G., Gagliardi, E. O., Leguizamón, M. G., & Hernández Peñalver, G. (2010). Globally optimal triangulations of minimum weight using Ant Colony Optimization metaheuristic. Journal of Computer Science and Technology, 10(02), p. 47–53. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/726
Issue
Section
Original Articles
