Comments on “algorithms for reporting and counting geometric intersections”

Abstract

Bentley and Ottmann <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> present 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 θ(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ).