3

To find all intersections of many line segments one can check every possible pair in O(n^2) for an intersection.

There is also the well-known Bentley-Ottmann_algorithm which uses sweep line approach to run more efficiently.

Are there any others, efficient, algorithms to find all the intersections?

At best, a survey of known and less-known algorithm would be very useful.

Ecir Hana
  • 10,864
  • 13
  • 67
  • 117
  • 1
    Did you have a look at [that section](http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm#Faster_algorithms) ? – Denys Séguret May 14 '14 at 12:57
  • @dystroy Yes, I did. I'm interested in any other ones, as well. – Ecir Hana May 14 '14 at 13:05
  • 1
    As the article mentions, there's a matching Omega(n log n) lower bound, unless you know more about your points. Isn't O(n log n + k) (Balaban) already pretty fast? o_O Also, note that the asymptotics might be misleading and hide gigantic constant factors. What's your application? – Niklas B. May 14 '14 at 13:12
  • @NiklasB. I'm interested in the various ways the problem can be solved, no application. – Ecir Hana May 14 '14 at 13:17
  • 1
    Seems a bit too broad to me for the Stack Exchange format – Niklas B. May 14 '14 at 13:26
  • @NiklasB. What's broad about asking for a survey of common geometry problem? – Ecir Hana May 14 '14 at 13:39
  • Well on second thought, maybe not. I'm actually not sure about this, so I'll retreat my close vote – Niklas B. May 14 '14 at 13:48
  • I use area sub-division for this http://stackoverflow.com/a/18739791/2521214 – Spektre May 15 '14 at 06:00
  • If there's no particular application, then you should chase citations using the publications cited by Wikipedia as a seed. Balaban is likely the last word in the computational geometry literature for the standard version of the problem. – David Eisenstat May 15 '14 at 14:29
  • @DavidEisenstat what do you mean "Balaban is likely the last word"? Is it simple, optimal, handles degenerate cases and has small constant factor? – Ecir Hana May 15 '14 at 15:06
  • That statement was intended more as a commentary on the priorities of computational geometers. It's not simple (but presumably a lot of people have looked for a simple, fast algorithm and failed), it is (asymptotically) optimal, figuring out the degenerate cases is an engineering problem (to a first approximation), and small constant factor is nontrivially correlated with simple (so again, there's presumably been a lot of failure). It's unlikely that many researchers would be thinking directly about this problem, but possible that they had a transferrable insight from something else. – David Eisenstat May 15 '14 at 15:14
  • @Ecir: why are you asking when you seem to know more then the respondents ?? Check "Computational geometry on a grid: an overview" by Mark Overmars. –  May 19 '14 at 07:42
  • @YvesDaoust maybe I misunderstood what you try to say but you are a respondent and I didn't know that paper. Obviously, if I knew more I wouldn't ask... – Ecir Hana May 19 '14 at 08:29

0 Answers0