For a simple connected graph with coordinates I believe this algorithm finds a path visiting every point once if it is possible.
The first step is to go to a point on the graph X, and find two points out of those that X is connected to, P and N, that maximizes this formula:
This will ensure that the vectors from P to X and from X to N are going around clockwise, and that the angle between them taken counterclockwise is maximized.
For the example above, this will make W=P and N=Y.
So we do this for every point on the graph:
And then eliminate any edges such that every point after removal is still connected to two other points. If this isn't possible than, you either already have the solution or it isn't possible to visit every point once and return to the original point.
**Idea for proof**
The formula being maximized is individual terms from the shoelace formula for polygons, so when each term is maximized the formula as a whole is maximized, and that must mean you have a closed polygon ordered clockwise which will visit every point once and return to the start.
http://en.wikipedia.org/wiki/Shoelace_formula
No comments:
Post a Comment