Find the shortest OPEN path connecting a set of 2D points (special case)

Question

I want to trace the shortest path between a set of points on 2D space. The points have integer coordinates and visually appear to follow a well-defined unique path, though they're disordered.

The precondition is very simple: For each point there's always a set of nearby points within a narrow arc, and another (possibly empty) set of nearby points within a narrow arc at a nearly opposite direction. There are no other nearby points.

For each set of three contiguous points within the path, namely A, B and C, the angle ∠ABC always has a measure between 90° and 270° (most of the time it's close to 180°, though there are a couple cases of points forming a nearly right angle), and the angles ∠BAC and ∠BCA have a measure of less than 90° (or possibly a smaller threshold).

My naïve idea is: for each point, evaluate the vectors toward the nearest n points to find whether there are two nearest opposite pairs and make the path piecewise (if all the other points are at nearly the same direction, then we're at the beginning or end of the path).

However, I want to know about a better way to trace the shortest path between the set of points, given the constraints above.

Edit: I forgot to say. No, I don't want a cycle. Though minimum Hamiltonian paths are still NP-hard, I...

You know what? I'll build a sparse graph that only contains the set of edges whose weight (Euclidean distance) is less than a threshold, then run Dijkstra's algorithm through the resulting adjacency list. This will work well with my data.

Answer 1

Your paths are varieties of what are often called angle-restricted paths in the literature, and exploring the literature may help with your particular situation:

• Fekete, Woeginger, 1997, "Angle-Restricted Tours in the plane."
• Dumitrescu, Pach, Tóth, 2009, "Drawing Hamiltonian cycles with no large angles."
• Bárány, Pór, and Valtr, 2009, "Paths with No Small Angles"

The general angle-restricted TSP (Traveling Salesman Path) problem is NP-hard, as established in the 1997 paper, "The Angular-Metric Traveling Salesman Problem."