I'm currently working on a project discussing applications of the Delaunay Triangulation, and the primary use-case is applications to TSP (or relaxations of the problem).

See: http://www.lancaster.ac.uk/staff/letchfoa/articles/triangulations.pdf for context.

One snag in the approach is that it occasionally produces non-Hamiltonian graphs (no Hamiltonian cycles). This forces us to consider relaxations of TSP where revists are allowed. In particular, given a Delaunay graph $G = (V,E)$, where the edges $E$ are weighted, I wish to find the minimum weight circuit when revisits are allowed.

I'm sure the usual heuristics apply here (nearest-neighbor, simulated annealing, ant colony, etc.) but I'm looking for any major research in this direction. I had difficulty finding anything substantial after a few hours research. This is perhaps because I'm having difficulty putting the problem into words, which brings me to my next question: is there a common name for this problem, so that I can search the literature more efficiently?

Thanks, Jon

PS: Attached is one such non-Hamiltonian triangulation. I had initially hoped these cases would be very uncommon, but unfortunately this one arose from a data set representing city locations (see: http://www.math.uwaterloo.ca/tsp/world/countries.html).

Non-Hamiltonian Graph Resulting from Delaunay Triangulation


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.