Apple Carving Algorithm to Approximate Traveling Salesman Problem from Compact Triangulation of Planar Point Sets
We propose a modified version of the Convex Hull algorithm for approximating minimum-length Hamiltonian cycle (TSP) in planar point sets. Starting from a full compact triangulation of a point set, our heuristic “carves out” candidate triangles with the minimal Triangle Inequality Measure until all points lie on the outer perimeter… Read full abstract & cite →