Apple carving algorithm to approximate traveling salesman problem from compact triangulation of planar point sets

Marko Dodig, Milton Smith

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)1-7
Number of pages7
JournalInternational Journal of Advanced Computer Science and Applications
Volume11
Issue number3
StatePublished - 2020

Keywords

  • Combinatorial optimization
  • Compact triangulation
  • Computational geometry
  • Heuristics
  • TSP

Fingerprint

Dive into the research topics of 'Apple carving algorithm to approximate traveling salesman problem from compact triangulation of planar point sets'. Together they form a unique fingerprint.

Cite this