Traveling Salesman - 2-Opt improvement

Question

So I've been looking for an explanation of a 2-opt improvement for the traveling salesman problem, and I get the jist of it, but I don't understand one thing.

I understand that IF two edges of a generated path cross each other, I can just switch two points and they will no longer cross. HOWEVER - I do not understand how I can determine whether or not two edges cross.

To make my question clear, this is what I've done so far: (I did it in java)

1. I have an object called Point that represents a city, with an x and y coordinate.
2. I have a PointSet which has a set of Points contained in a List.
3. I have a method for PointSet called computeByNN() which arranges the PointSet in a fairly short manner through a Nearest Neighbor algorithm.

So now I have a sorted PointSet (not optimal, but still short) and I want to do 2-opt on it. However, I don't know where to start. Should I check each and every line segment to see if they cross, and if they do, switch two points? I feel like that defeats the purpose of heuristics and it becomes a sort of brute force solution. Is there an efficient way to find if two segments of the tour cross?

I applogize if my question is not clear. I'll try to edit it to make it clearer if anyone needs me to.

Answer 1

If you like you can create a look-up table to detect crossed edges. For n = 1000, order 10^12 entries is obviously too extravagant. However you probably are most worried about the shorter edges? Suppose you aimed to include edges to about √n of the nearest neighbors for each node. Then you are only in the realm of megabytes of space and in any case O(n^2) preprocessing. From there it's a heuristic, so good luck!

Also will mention this can be done on the fly.