TY - JOUR

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

AU - Dodig, Marko

AU - Smith, Milton

N1 - Publisher Copyright:
© 2020, Science and Information Organization.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Combinatorial optimization

KW - Compact triangulation

KW - Computational geometry

KW - Heuristics

KW - TSP

UR - http://www.scopus.com/inward/record.url?scp=85083191250&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85083191250

VL - 11

SP - 1

EP - 7

JO - International Journal of Advanced Computer Science and Applications

JF - International Journal of Advanced Computer Science and Applications

SN - 2158-107X

IS - 3

ER -