Heuristic for the Hamiltonian Path Problem in Euclidian Two Space

The Hamiltonian Path problem is a variant of the travelling salesman problem, in which the tour is not a closed curve. It has been demonstrated that the optimal path through all the points in some finite subset of Euclidian two space must take the vertices of each "half" of the convex hull in the order prescribed by the convex hull. This fact is used to develop two heuristics. These are tested against problems for which the optimal solution is determined by other methods. These comparisons as well as measures of computational efficiency are presented.