Convex Hull and Incremental Insertion for a TSP Solution
Ishani Das, Tuli Bakshi · 2025
In this paper, current researchers have dealt with heuristic solution of famous Traveling Salesman Problem. Being an NP-hard problem, since its formulation, several heuristic solutions have been tried. The greedy mechanism is one of the well-known design styles of the algorithm. The computational geometric algorithm, using a convex hull, has been experimented to cover the space into a convex polygon. It can be done easily by any well-known algorithm. Next, it has been shown that within the convex problem space, an optimal possible Hamiltonian cycle has been found.This Hamiltonian cycle is the solution of the TSP. Experiment on the benchmark test cases and the theoretical findings.