title: Delaunay Triangulation Equivalent for Undirected Graph
body: <p>I'm working on a path planning algorithm that is equivalent to a traveling salesman problem. I don't know how many nodes I might have so I'm willing to sacrifice accuracy for speed. My problem can be modeled as a fully connected graph, with the cost of transitioning between nodes being related to more than just the distance between nodes. I'd like to restrict my search space to connections that lie on the delaunay triangulation (the research I've read notes that 95-100% of connections in solutions to the TSP lie on the delaunay triangulation) but since my graph cannot be expressed as 2D or even 3D geometry, I can't directly use it in my representation. Is there an algorithm that results in an equivalent triangulation to the delaunay triangulation that applies to graphs that do not conform to a geometric representation (cost of connections cannot be expressed as a geometric distance between points due to over-constraint)?</p>