Software Development

I was then trying to expand on this idea and take the next point that provides the shortest path by connecting two points on the convex hull and rerouting it through this nearest point. This too is known to be the shortest path for those points on the currently existing path (if we omit the other points).

What I wanted to find out is when does taking the nearest point after this result in a path that is no longer the shortest path. I found my answer. Take a look.

(Click on image for larger view)


This is a classic example that exemplifies the issue at hand. All points except the ones in red are part of the convex hull. The shortest path is in yellow while my algorithm is in blue. You can see I'm short by 7.5 pixels where the path lengths are displayed at the bottom.

What my algorithm does is pick the point that will give the next shortest path. That point is B when connected as displayed in the graph above (but point A would not be connected yet). Then it picks the next shortest path which is when point A gets connected.

The reason this doesn't always end up being the shortest path overall is because the two points A and B are meant to be connected to the same two points from the convex hull. The combination of A and B creates a shorter path than selecting one point at a time.

While I still have a NP-complete problem, it is nice to be able to subdivide the problem in this manner. One can indeed start off with the convex hull and then you have to figure out what groups of points need to be connected to what pairs of points on the convex hull. I don't even need to know how those points are connected because once I have those points, I can reuse the same algorithm to create a NEW convex hull with those points and the algorithm becomes recursive and polynomial in running time. The issue is figuring out what groups of points are to be connected to each pair of points on the convex hull.

I could easily fix the problem shown in the above image for that special case. But that would be the wrong way to go. I need to figure out the general case for any number of points connected to the same pair of points on the convex hull.

Unfortunately, it can be very difficult to determine when two or more points (not on the convex hull) need to be connected together. Say point A is closest to points X and Y (where X and Y are on the convex hull) and that point B is closest to points W and Z (where W and Z are on the convex hull). There are situations where A and B should be connected together and then linked up to points M and N (where M and N are on the convex hull). This means we can't even use the nearest points on the convex hull as a guide as shown in the following image.

(Click on image for larger view)


I have a few ideas I want to try, but I'm only doing this for fun. I was interested in finding out why the nearest neighbour would not work and used it as a way to get back into programming my main project by using its framework for my TSP program. Still, TSP is a problem that everyone understands and one always finds out new information by having a go at it. For example, the straight skeleton is different than what I was using. The straight skeleton creates areas based on distance from the edge while my algorithm creates areas based on distances to pairs of vertices (where the boundaries are actually oval intersections).

UPDATE Nov 7, 2009

I fixed the issues found above so that if two points taken together are shorter than the shortest path taken when the points are considered individually, then the shortest path with the two points taken together will be chosen. So all the issues I talked about earlier are solved.

What remains is determining if it's possible that three or more points have shorter paths than when those points are taken individually or in pairs. ALSO!!! And this is important... the shortest path of any two points out of the three cannot be where they belong. IOW, Say points A,B and C belong between hull points X and Y (for example, the path could be X->A->B->C->Y), then no pair {A,B}, {B,C} and {A,C} can be the shortest path when linked up to X and Y when only considering those two points.

I have no idea how to figure this out if it's possible. It seems really unlikely. Anyhow, I need to find long paths that have already been solved. I can now test instantly cases up to about H+C points where H is the number of points on the hull and C is about 7. The number of points on the hull doesn't matter. It can be anything, even be in the millions.

If my algorithm has any issues finding the shortest path, it happens extremely rarely. But as I said, I can only test about a dozen points. If I had a list of points that were already solved, I could test my algorithm some more.