Reporting and counting segment intersections (Q1821557)

The author presents an algorithm for listing all segment intersections in the plane. The running time of the algorithm is \(O(n(\log^ 2n/\log \log n)+k)\), where n is the number of segments and k is the number of intersections. In order to construct the algorithm the author uses divide and conquer strategy and a new geometrical notion which he calls hammock. Using a result of \textit{H. Edelsbrunner} and \textit{E. Welzel} [Halfplanar range search in linear space and \(O(n^{0.695})\) query time, Tech. Univ. Graz. IIG Report 111 (1983)], he constructs an algorithm for evaluating the number of intersecting pairs of segmets with running time \(O(n^{1.695})\).