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 of the remaining partial triangulation. The initial candidate list consists of triangles on the convex hull of a given planar point set; the list is updated as triangles are eliminated and new triangles are thereby exposed. We show that the time and space complexity of the “apple carving” algorithm are O(n2) and O(n), respectively. We test our algorithm using a well-known problem subset and demonstrate that our proposed algorithm outperforms nearly all other TSP tour construction heuristics.

@article{Dodig2020,
  title     = {Apple Carving Algorithm to Approximate Traveling Salesman Problem from Compact Triangulation of Planar Point Sets},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {11},
  number    = {3},
  year      = {2020},
  publisher = {The Science and Information Organization},
  author    = {Marko Dodig and Milton Smith},
  doi       = {10.14569/IJACSA.2020.0110301},
  url       = {https://doi.org/10.14569/IJACSA.2020.0110301}
}