Ivan Balaban's Optimal Algorithm in O(n log n + k)

[HansBrende]

It would be worth adding Ivan Balaban's "Optimal Algorithm" which hits the theoretical lower bound for segment intersection time and space complexity of O(n log n + k) and O(n), respectively.

Here is a link to his paper: https://www2.cs.sfu.ca/~binay/813.2011/Balaban.pdf

Also, he seems to have created a C++ implementation here: https://github.com/ivvaan/balaban-segments-intersections

Some additional work would need to be done to handle degenerate cases.

[anvaka]

thank you for the tip! If anyone wants to implement it - I'd be happy to take a pull request!