10

Suppose I have n line segments in general position. How can I quickly count, for each of my n segments, how many of the other n-1 it intersects?

I can do this naively in O(n2) time. I can find all intersections using a fairly straightforward sweep line algorithm (Bentley-Ottmann) in O((n + k) log n) time, where k is the number of such intersections, and then aggregate the intersections I found into a bunch of counts.

I don't need to find the intersections, though; I just want to know how many there are. I don't see how to modify the sweep line algorithm to be faster since it needs to reorder two things in a tree for every intersection, and I can't think of any other techniques that don't suffer from the same problem.

I'm also interested in hearing how to count how many total intersections there are.

tmyklebu
  • 13,915
  • 3
  • 28
  • 57

1 Answers1

7

I have a hard time believing that you can do better than Bentley Ottman in the general case. You can simplify the computation a bit if you don't care where the line segments intersect, but I don't see how you could count crossings without finding them.

In essence, Bentley Ottman is a way to simplify the search space for intersections. There are other ways, which might work for particular arrangements of line segments, but unless there is some predictable geometric relationship between your segments, you're not going to be able to better than first using some clever way of finding candidate intersections combined with an individual verification of each candidate.

Unless your problem domain has some specific features which might make provide exploitable substructure, I'd think your best bet for speed would be to adapt Bentley Ottman (or some similar sweeping algorithm) for parallel execution. (Clipping the line segments into bands is a simple one. Figuring out an optimal set of bands would be interesting, too.) Of course, that's a practical rather than an academic exercise; the parallel algorithm might well end up doing more work in total; it just exploits hardware to do the work in (a constant factor) less time.

rici
  • 234,347
  • 28
  • 237
  • 341
  • 2
    I have...less of a hard time believing the sweep line method can be beaten. Consider that I can count the number of intersections between n line segments whose left endpoints all have x-coordinate 0 and whose right endpoints all have x-coordinate 1; this is just the classical problem of counting inversions in an array. So, at least in some special cases, I should be able to look for this kind of substructure and exploit it somehow. – tmyklebu Dec 23 '12 at 09:54
  • @tmyklebu, sure, if there is an exploitable substructure, you can readily exploit it. But you have to know about it first. You could check for the unit square case easily, in `O(n)`, but it would be silly unless you had good reason to believe it was likely. (And similarly for other special cases, like a collection of convex polygons.) Such cases are not "the general case". B-O will handle the collection of polygons case nicely, because it speeds up with fewer actual intersections. – rici Dec 23 '12 at 16:50
  • B-O handles the case where only few intersections exist nicely. I can still come up with rough cases when I've got a bunch of polygons (picture a whole bunch of equilateral triangles centred at the same point but rotated by random angles). Exploitable substructures are...kind of the point of the question. :) There's a paper by Chazelle ("Reporting and counting segment intersections") that seems to use this vertical decomposition idea and purports to have an O(n1.695) time algorithm for my problem, but it seems to rely on a very impractical data structure. Better than nothing. – tmyklebu Dec 23 '12 at 18:12
  • The difference between n^2 and n^1.695 is about 70:1 for 10^6. So for an algorithm like that to be practical (assuming a million line segments is in the normal problem domain) it has to do no less than 70 times as much work in whatever passes for its inner loop. As I understand Welzl's work, which that solution is based upon, the main cost would be the construction of the conjugation trees, but maybe I've got that wrong. The lookup is more work than running through a quadtree, but it's just a bit of algebra. I think that's all a fascinating academic exercise. Have fun with it.... – rici Dec 24 '12 at 01:14