Designing Hamiltonian Cycles

Abstract

Historically, the minimal length Hamiltonian cycles in a random point cloud lying inside a given rectangle are computed by partitioning this rectangle. We have used successive convex hulls of the set of points, in order to obtain partitions better suited for this purpose. The free computer algebra system Sage has been very useful to perform the corresponding computations (for sets of 100 to 200 points, the result is obtained in just 15 seconds using a laptop computer running Ubuntu 12.04 with an Intel Core i7-2630QM processor and 8GB of RAM). The code developed is also applied with success to obtain good approximations of minimal length Hamiltonian cycles, across the major cities of the countries of the European Union. In each country, Ei, we make a transverse Mercator representation centered in the point Ci of average latitude and average longitude among the selected cities in the country. For a list of countries [E1, · · ·,En] we paste in the origin of the complex plane the local chart of E1. Then, the local chart of E2 is translated by the complex number whose modulus is the geodesic distance (C1,C2) and whose argument is the angle between the maximal circle (C1,C2) and the parallel of C1, and so successively until En. In this way, all the cities are transformed into a set of points in the complex plane where each pair can be connected by a straight line.