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

fYear

2010

fDate

23-26 March 2010

Firstpage

81

Lastpage

85

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ICCSA.2010.38

Filename

5476619