Comments on “algorithms for reporting and counting geometric intersections”
Kevin Q. Brown · IEEE Transactions on Computers · 1981
Bentley and Ottmann1present an algorithm for reporting all K intersections among N planar line segments in 0((N + K) log N) time and 0(N + K) storage. With a small modification that storage requirement can be reduced to 0(N) with no increase in computation time, which is important because K can grow as θ(N2).