Title :
An Ant Colony Algorithm for the Minimum Weight Triangulation
Author :
Jahani, Malihe ; Bigham, Bahram Sadeghi ; Askari, Abbas
Author_Institution :
Dept. of Comput. Sci., Inst. for Adv. Studies in Basic Sci. (IASBS), Zanjan, Iran
Abstract :
A triangulation of a planar set S is a maximal plane straight-line graph with the vertex set S. In the Minimum Weight Triangulation (MWT) problem, we want to draw a triangulation of a given point set that minimizes the sum of the edges length. Recently, Mulzer and Rote have proved that this problem is NP-Hard. In this paper, we present a heuristic algorithm using Ant Colony Optimization to solve this problem.
Keywords :
computational complexity; computational geometry; graph theory; minimisation; NP-hard problem; ant colony algorithm; edge length minimization; heuristic algorithm; minimum weight triangulation; straight-line graph; Ant colony optimization; Application software; Approximation methods; Computational geometry; Computer graphics; Computer science; Data analysis; Heuristic algorithms; Joining processes; Polynomials; Ant Colony Optimization; Computational Geometry; MWT; Minimum Weight Triangulation;
Conference_Titel :
Computational Science and Its Applications (ICCSA), 2010 International Conference on
Conference_Location :
Fukuoka
Print_ISBN :
978-0-7695-3999-7
Electronic_ISBN :
978-1-4244-6462-3
DOI :
10.1109/ICCSA.2010.38
