2

I have a set of lines and I want to count how many pairs of these lines intersect inside of some circle.

This supposed to be solvable in O(nlogn) using sweep line algorithm. What I've done is I've first found all line segments inside of a circle (that is, for each line I computed both intersections with the circle and got the line segment, but if there is no intersection, I just ignored that line).

Then, I tryed adopting Bentley-Ottmann algorithm, but for it to be O(nlogn) instead of O((n+k)logn), where k is the number of all intersections, I would have to skip the part of the algorithm, which inserts intersections into the event queue and process them just as it processes the endpoints of all the found line segments, but then the algorithm wouldn't work, so no go (related: Is there an efficient way to count the number of intersections among a given set of line segments?)

Basically, I can't find any particular exploit for this problem, which would make the sweep line algorithm O(nlogn). The things that can be exploited here are the facts that we are basically seeking intersections among line segments (chords!) inside of the circle, and that we only need to count them (more preciselly, how many pairs of line segments have intersections between them, so duplicates can occur!).

user2340939
  • 1,791
  • 2
  • 17
  • 44
  • 1
    I suppose you cannot assume that none of the line segments terminate inside the circle. If you could assume that, you might be able to do something clever by traversing the intersections around the circumference of the circle. But if you cannot assume that, the problem cannot be easier then the general intersection problem because you can find a circle which encloses n line segments in O(n). – rici Apr 09 '17 at 05:05
  • You have a set of chords with endpoints on the same circle, so your problem becomes one-dimensional one (well, it's still the circle). Please see: http://stackoverflow.com/questions/19085937/finding-intervals-of-a-set-that-are-overlapping – HEKTO Apr 12 '17 at 15:34
  • If you would like to get rid of `k` in `O` then you are mostly interested in cases where more than two lines intersect in the same point? – Fedor Oct 16 '22 at 08:39

0 Answers0