An Algorithm For Computing A Hamiltonian Cycle Of Given Points In A Polygonal Region

The problem of computing a Hamiltonian cycle of given points in a simple polygon is a novel transformation of the classical Hamiltonian problems.The research on this issue involves computational geometry and graph theory,which is of relatively high theoretical value.In addition,stand on the application point,to the fields such as robotics,game industry,maritime search and rescue,military operations,logistics planning,traffic planning,traffic navigation,social networking,Internet of Things and physical search and UAV controls,the value of studying on this problem is also obvious.In this paper,computing a Hamiltonian cycle of given points in a simple polygon is seriously studied.First,the basic knowledge and concepts related to the problem are described,for example:Hamiltonian path,Hamiltonian cycle,geodesic convex hull,simple path,and their extensions limited in a polygon,etc.Then,some existing related researches are also summarized and analyzed in this paper,for example,the solution of Hamiltonian path and cycle in particular types of graphs,the construction of geodesic convex hulls and the solution of simple paths in polygons.Due to the situation that no targeted and feasible algorithm is given for the problem of computing a Hamiltonian cycle of given points in a simple polygon as well as the difference between our problem and the general Hamiltonian problems in graphs,therefore,finding the potential order of the given set of points is the main direction of our study.Firstly,a cycle built on the points in a subset of the given point set,which can determines the potential order of partial points,is pre-computed in the given polygon.Secondly,the Hamiltonian cycle is built by inserting the remaining points one by one into the initial cycle.With this method,we can find a polynomial time algorithm to solve this problem.On the basis of before-mentioned,a corresponding algorithm is designed and a detailed analysis of its performance is carried out.Lastly,we encode this algorithm in the case that the number of given points is less than 100.The results show that our algorithm is feasible and efficient.