Efficient way to find intersections

Problem Detail: 

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.

Asked By : Ilya_Gazman

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16418