Nicolau Andres Thio is a Bachelors Student in the School of Mathematics (with a specialisation in Discrete Maths and Operations Research) at The University of Melbourne. He is interested in Computability and Complexity Theory, and their application to Operations Research and Graph Theory.
An Heuristic Algorithm for the Minimum Weight Triangulation Problem
A triangulation is an edge-maximal graph on a set of points S such that no pair of edges intersect. This means that no new edges can be added to a triangulation that would not intersect any of the existing edges. Therefore a triangulation is a plane graph where every interior face is a triangle, and the boundary of the exterior face coincides with the convex hull of S. The minimum weight triangulation problem consists on finding a triangulation of S such that the sum of the Euclidean lengths of the edges is a minimum.
This problem has been labelled as one of the most important problems in computational geometry, and was only proven to be NP-Hard in 2006. As is common with NP-Hard problems, a strong interest on approximation algorithms and heuristics for the problem has developed. Finding fast and accurate algorithms has been the aim of many studies over the years.
It has been shown that a variety of specific proximity graphs must be subgraphs of a minimum weight triangulation. In addition, many polynomial time algorithms have been discovered that construct minimum weight triangulations for sets of vertices with given properties.
In this project we looked at creating a new approximation algorithm making use of the existing subgraphs for points in general position, and testing its performance against other known triangulations such as the Greedy and the Delaunay. We used a combined adaptation of Kruskal’s and Convex Polygon Triangulation algorithms to create a triangulation that was always better than the Greedy and Delaunay triangulation. We also tried to locally optimize all three triangulations with a local search, which improved the Delaunay triangulation but did not improve ours. This has allowed us to conclude that the algorithm presented is locally optimal and always behave better than both the Greedy and the Delaunay triangulations.