An Ant Colony Algorithm for the Minimum Weight Triangulation

2010/01/01 by Malihe Jahani, Bahram Sadeghi Bigham, Abbas Askari · 3 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Constraint Satisfaction and Optimization #Minimum-weight triangulation #Triangulation #Point set triangulation #Delaunay triangulation #Pitteway triangulation #Vertex (graph theory) #Bowyer–Watson algorithm #Ant colony optimization algorithms #Mathematics #Algorithm #Constrained Delaunay triangulation #Set (abstract data type) #Computer science #Heuristic #Combinatorics #Mathematical optimization #Graph

paper · doi:10.1109/iccsa.2010.38

openalex publication_date 2010/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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.

Citations

• Minimal Triangulations of Polygonal Domains
• Neither the greedy nor the delaunay triangulation of a planar point set approximates the optimal triangulation
• The drawability problem for minimum weight triangulations
• Computing a subgraph of the minimum weight triangulation
• Closest-point problems
• Polynomial-time instances of the minimum weight triangulation problem
• An O(n2log n) time algorithm for the MinMax angle triangulation
• A note on Delaunay and optimal triangulations
• On triangulations of a set of points in the plane
• Minimum-weight triangulation is NP-hard
• Ant Algorithms for Discrete Optimization
• A chain decomposition algorithm for the proof of a property on minimum weight triangulations

Cited by

• Minimum-weight triangulation [wikipedia]