2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What research have you done? What have you tried? We expect you to do some research on your own before asking. Are you familiar with standard computer graphics algorithms to test whether two line segments intersect each other? $\endgroup$ – D.W. Oct 25 '13 at 7:31
  • $\begingroup$ @D.W. No, in my TSP program I just use simple math function, that I wrote by myself. $\endgroup$ – Ilya Gazman Oct 25 '13 at 11:05
11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.