A Linear-Time Greedy Approach With Directional Optimization for Minimum Weight Triangulation of Convex Polygons

Minimum Weight Triangulation (MWT) of convex polygons is a cornerstone problem in computational geometry with applications in mesh generation, terrain modeling, computer vision, and geographic information systems. Traditional dynamic programming approaches solve MWT exactly but incur prohibitive <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup>) time complexity, limiting their scalability for large polygons. This paper introduces a novel greedy algorithm that achieves optimal MWT in linear <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>) time by starting from the shortest edge and iteratively selecting the minimal diagonal among four consecutive vertices, enhanced with directional optimization (clockwise and anticlockwise traversals) to exploit geometric configurations and yield a superior result. Our contributions include: (i) a mathematically rigorous formulation and proof-of-concept implementation that balances efficiency and accuracy; (ii) directional traversal strategies that improve solution quality by up to 10 % in tested cases; (iii) comprehensive experimental validation on diverse convex polygons (4 to 15 vertices), demonstrating weights within 3:5 % of optimal DP solutions while outperforming quasi-greedy and Delaunay methods by 20 – 30 % and over 10<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i>, respectively; and (iv) runtime scalability analysis showing orders-of-magnitude speedups for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> ≥ 50. Compared to state-of-the-art methods, our approach offers a practical, lightweight alternative for real-time applications, with code available at https://github.com/drmasifhabib/MWT_Greedy_Algorithm. This work advances efficient approximation algorithms for NP-hard geometric optimization, paving the way for hybrid methods in largescale computational geometry tasks.