I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.I am randomly creating a path thru all the vertices and I want to know if there is any efficient way to find all the intersections on my path.
Efficient way to find intersections
algorithms;graphs;graph traversal;weighted graphs
A path of length $n$ consists of $n$ line segments in the plane.  You want to find all intersections between these line segments.  This is a standard problem that has been studied in depth in the computer graphics literature.A simple algorithm is the following: for each pair of line segments, check whether they intersect (using a standard geometric algorithm).  The running time of this algorithm is $O(n^2)$.  In terms of worst-case complexity, this is the best we can hope for, as in the worst case, there can be $\Theta(n^2)$ intersections, so obviously it'll take at least $\Theta(n^2)$ time to output them all.However, in many cases, we have an arrangement of line segments where there are only a few intersections, say at most $O(n)$ intersections.  In this case, there are algorithms whose running time is $O(n \lg n)$.  See, e.g., the sweep line technique; there are others as well.  In general, if there are $k$ intersections, the total running time for the sweep line algorithm to find all $k$ intersections is $O((n+k) \lg n)$ time.