Is there an efficient way to count the number of intersections between a given set of line segments?

Question

Suppose I have n segments in general position. How can I quickly calculate for each of my n segments how many other n-1 it crosses?

I can do it naively in O (n ² ) time. I can find all the intersections using the fairly simple Bentley-Ottmann algorithm in O ((n + k) log n) time, where k is the number of such intersections, and then aggregating the intersections I found in the heap matters.

I do not need to look for intersections; I just want to know how many there are. I don’t see how to change the scan line algorithm faster, since for each intersection it is necessary to reorder two things in the tree, and I can’t think of any other methods that do not suffer from the same problem.

I am also interested in hearing how to count the number of full intersections.

Answer 1

I find it hard to believe that you can do better than Bentley Ottman in the general case. You can simplify the calculation a little if you don't care where the line segments intersect, but I don’t see how you could calculate the transitions without finding them.

In essence, Bentley Ottman is a way to simplify the search space for intersections. There are other ways that can work for specific line segment patterns, but if there is no predictable geometric relationship between your segments, you may not be better than using the smart way to find candidate intersections in combination with an individual check of each candidate .

If your problem domain does not have any specific functions that could provide an operational substructure, I would think that the best option for speed would be to adapt Bentley Ottman (or some similar sweeping algorithm) for parallel execution. (Cutting off line segments in stripes is simple. Determining the optimal set of stripes would also be interesting.) Of course, this is a practical, not an academic exercise; a parallel algorithm may well ultimately do more work; it just uses hardware to do the job (constant factor) less time.